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

大家好,我是吴师兄。

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