大家好，我是吴师兄。
今天的标题来源于 LeetCode 第 518 号问题零钱兑换II的评论：
有这么骚气的评论，索性把零钱兑换的两题都学习一下吧：
两道类似的题目，首先来看第一道，给定一个数值以及硬币的面值，问组合成这个面值最少需要硬币的个数。
找题目中的关键点，“填充面值”，“最少个数”，基本上可以确定是动态规划中背包一类的问题。
背包一类问题的特殊的地方就是用值来当作 DP 的状态。
我们可以根据题目中的条件关系来确定状态， dp[i][j] 表示的意义是 “用面值为 coins[0]...coins[i] 的货币填充数值 j 最少需要的个数”。
确定完状态，接下来就是找到状态之间的联系，也就是写出递推关系式：
“dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - coins[i]] 1, dp[i][j - coins[i]] 1) ”
解释一下这个关系式是怎么写出来的。
每当我们考虑一个状态的时候，比如 dp[i][j]，我们需要去思考一个问题，那就是得到 j 用不用当前的面值进行填充。
1、如果不用，那么就是前一个状态的顺延，也就是 dp[i - 1][j]。
2、如果用，那就是 dp[i - 1][j - coins[i]] 1 或者是 dp[i][j - coins[i]] 1。
这里之所以有两个状态是因为当前考虑的面值可以用无数次。
那怎么确定到底是这几个状态中的哪一个呢？
取最小值，因为题目要求的是最小。
这里只是为了解释清楚，所以把所有可能的状态都列了出来，但是我们在计算 dp[i][j - coins[i]] 1 的时候，已经考虑过 dp[i - 1][j - coins[i]] 1 了，所以不需要重复考虑，因此可以把递推关系进一步简化：
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] 1)
写到这里，你发现了一个有趣的现象:虽然我们需要二维的 DP 数组来表示这么一个递推关系，但是实际我们并不需要二维数组。
这也很好解释，dp[i][j] 与 dp[i][j - coins[i]] 同属一维，dp[i][j] 与 dp[i - 1][j] 看似需要用二维表示，但其实完全可以把它们放在同一个维度，并不会对后面的状态推导造成影响，处于节省空间的目的，我们还可以简化：
dp[j] = min(dp[j], dp[j - coins[i]] 1)
知道了上面这些，基本上实现就没什么难的了，无非是考虑一些初始化和越界的问题。
第二道题目和第一道题目同属一类问题，只不过是第二道题求的是组合个数。
状态定义上没有区别，不一样的只是状态之间的关系，也就是递推关系。
你可以试着参照我上面的推导过程，看能不能推导出最优的关系式。
给出这两题的参考代码来：
代码语言：javascript复制// 322. 零钱兑换 I
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < coins.length; i) {
for (int j = coins[i]; j <= amount; j) {
if (dp[j - coins[i]] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j - coins[i]] 1, dp[j]);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// 518. 零钱兑换 II
public int change(int amount, int[] coins) {
int[] dp = new int[amount 1];
dp[0] = 1;
for (int i = 0; i < coins.length; i) {
for (int j = coins[i]; j <= amount; j) {
dp[j] = dp[j - coins[i]];
}
}
return dp[amount];
}
最后
这是我们每天学会一点知识的第 44 天，当前进度 44/100。
我已经将大部分算法题解文章同步到了个人网站，方便阅读。
“网站地址：https://www.cxyxiaowu.com/”
