女朋友睡了自己偷摸摸爬起来做题，就是这个题有点简单了

发布于

大家好，我是吴师兄。

今天的标题来源于 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];



}
代码语言：javascript
复制
// 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/”

#dp#min#ode