leetcode 322 找零钱
这道题本质上还是要3重循环来做的，只不过可以进行优化变成两重循环，在了解优化思路之前如果直接看答案肯定会懵。因为我们无法了解到优化是从哪里来的。
dp最核心的思想是要明白你f[i][j] 表达的是什么样的集合。 对于这道题，因为你每个coin能够选择无限多次，那么f[i][j] 实际上就表达的是当前第i个coin在j amount 下面你能够选择最小的数从而凑出j。
那么一开始我们每个dp[i][j]里面都要设置成最大数，只有能够正好找零才更新dp[i][j]。所以初始化的时候，dp[0][j] 只有在coin上面有更新，下面是初始化部分的代码
int[][] dp = new int[n+1][amount+1];
for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= amount; j++) {
for (int k = 0; k * coins[i] <= j; k++) {
if (dp[0][j - k * coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - k *coins[i]] + k);
}
}
}
n就是第几个coin， amount就是你要凑出的数目当amount - k*coins[i] == 0的时候，你就找到一个刚好凑出这个数目的最小数目了。所以dp[0][j] 就是一个包含每个零钱选任意次而能够凑出j这个数目的最小数的集合
初始化过后你就可以从第1个到第n个coin 进行循环，然后每个coin都尝试k次，判断条件就是k*coin 要小于amount并且dp[i-1][j - k * coin] 不是最大数，因为我们初始化过了，所以dp[i-1]就代表最开始零钱能够凑出j的数字。然后记录下来最小值，代码如下
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
int n = coins.length;
int[][] dp = new int[n+1][amount+1];
for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= amount; j++) {
for (int k = 0; k * coins[i] <= j; k++) {
if (j >= coins[i] && dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
}
// if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
}
}
// System.out.println(Arrays.toString(dp[0]));
for (int i = 1; i <= n; i++) {
dp[i][0] = 0;
for (int j = 0; j <= amount; j++) {
for (int k = 0; k * coins[i-1] <= j; k++) {
if (dp[i-1][j - k * coins[i-1]] != Integer.MAX_VALUE) dp[i][j] = Math.min(dp[i-1][j], dp[i][j - k *coins[i-1]] + k);
}
}
// System.out.println(Arrays.toString(dp[i]));
}
if (dp[n][amount] == Integer.MAX_VALUE) return -1;
return dp[n][amount];
优化
明白了底层逻辑后，我们就可以尝试优化了，因为我们第三层循环就是在不断试当前coin取多少次可以凑出j，那么我们在刚开始初始化的时候，已经计算出了当前每个coin能够凑出j的最小值，那么我们在之前算过的基础上在j-coin[i] == 0 的基础上 + 1就好了。下面是简单优化过的版本（这里只优化了时间维度），后面还会有一个空间维度的优化）
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
int n = coins.length;
int[][] dp = new int[n+1][amount+1];
for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
// for (int k = 0; k * coins[i] <= j; k++) {
if (dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
// }
// if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
}
}
System.out.println(Arrays.toString(dp[0]));
for (int i = 1; i <= n; i++) {
dp[i][0] = 0;
for (int j = 0; j <= amount; j++) {
// for (int k = 0; k * coins[i-1] <= j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]);
if (j >= coins[i-1] && dp[i][j - coins[i-1]] != Integer.MAX_VALUE) dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i-1]] + 1);
// }
}
// System.out.println(Arrays.toString(dp[i]));
}
if (dp[n][amount] == Integer.MAX_VALUE) return -1;
return dp[n][amount];
}
被注释掉的部分就是我们优化的部分，这样也方便你看出我对哪里进行了优化。
空间优化
因为完全背包是基于前面计算过的最小数或者最大数，那么我们就可以把空间压缩成一维。代码如下
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
int n = coins.length;
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
// for (int i = 0; i < n; i++) {
// for (int j = coins[i]; j <= amount; j++) {
// // for (int k = 0; k * coins[i] <= j; k++) {
// if (dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
// // }
// // if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
// }
// }
// System.out.println(Arrays.toString(dp[0]));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
// for (int k = 0; k * coins[i-1] <= j; k++) {
if (j >= coins[i-1] && dp[j - coins[i-1]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coins[i-1]] + 1);
// }
}
// System.out.println(Arrays.toString(dp[i]));
}
if (dp[amount] == Integer.MAX_VALUE) return -1;
return dp[amount];
}
