今天在leetcode上做了几道dynamic programming的题。就其中两道题做个总结吧。
Coin change
先从第一道题讲起，题目大意是：有不同面值的硬币，以及一个需要由各种硬币组成的数字，需要找出最少要几个硬币才能组成这个数字。（每种面值的硬币的数量都是无穷的）。如果硬币无法组成这个数字，返回-1。
这是一个例子，下面的讲解也用这个例子：
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
这是一个一眼看上去就比较典型的dp问题，我直观地想到的解法就是
1. 直接使用recursion方法
一开始，我直接使用上面这个总结出来的公式，写出了如下代码，显然是不符合时间复杂度的。但是可以作为优化的起点。
class Solution {
public int coinChange(int[] coins, int amount) {
//f(n) = 1 + min(f(n-1), f(n-5), f(n-10))
// 1 5 10 is type of coin
if(amount == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(amount - coin >= 0) {
res = Math.min(res, coinChange(coins, amount-coin));
}
}
return (res == Integer.MAX_VALUE || res < 0)?-1:res+1;
}
}
2. 优化recursion方法
根据前面一篇dynamic programming文章提到的，对recursion进行优化，可以用一个array将已经计算过的东西储存起来，避免重复运算。
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) {
return 0;
}
int[] cache = new int[amount+1];
Arrays.fill(cache, -1);
for(int coin: coins) {
if(coin <= amount) {
cache[coin] = 1;
}
}
return coinChange(coins, amount, cache);
}
public int coinChange(int[] coins, int amount, int[] cache) {
if(cache[amount] >= 0) {
return cache[amount];
}
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(amount-coin >= 0) {
res = Math.min(res, coinChange(coins, amount-coin, cache));
}
}
cache[amount] = (res == Integer.MAX_VALUE || res < 0)?-1:res+1;
return cache[amount];
}
}
优化过的recursion代码思想还是和之前的一致的，只是增加了cache变量。
3. 将从上到下转化为从下到上
Dynamic programming最重要的一步。之前的recursion代码是从上到下的一个过程，在这一步需要将它转化为从下到上，去除recursion过程，因为recursion往往会需要更多的space。
下面是代码
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) {
return 0;
}
int[] cache = new int[amount+1];
Arrays.fill(cache, -1);
for(int coin: coins) {
if(coin <= amount) {
cache[coin] = 1;
}
}
for(int i = 1; i <= amount; i++) {
if(cache[i] >= 0) {
continue;
} else {
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(i-coin >= 0 && cache[i-coin]!=-1) {
res = Math.min(res, cache[i-coin]+1);
}
cache[i] = (res==Integer.MAX_VALUE||res<=0)?-1:res;
}
}
}
return cache[amount];
}
}
之后在discussion看到了更加简洁的答案：
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
总结
从整体的解答思想和一步一步得到danamic programming解法的过程来说，我的解答完全遵循前面一篇文章中提到的步骤。我在解题过程中遇到的最大的问题不是代码的逻辑，而是edge case的处理和array的initial value，其实这两个是同一个问题。我做了很多种不同的尝试，但是最后都没有写出和讨论区看到的解答那样简洁的答案。
通过学习别人的代码，我学习到的：根据迭代的方法设立好的初始值对edge case来说至关重要。但是还没能总结出什么规律，还需要多学习别人的解答。不要总盯着0，1，-1，Integer.MAX_VALUE，Integer.Min_VALUE不放。
网友评论