LeetCode 518 Coin Change 2 硬币问题

发表于 | 阅读次数:

题目链接：518. Coin Change 2

我的源码：源码

最近看到这道题，但是看网大部分教程感觉思路都写的不是特别的详细。分享一下个人的解题思路。

题目：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:
1
2
3
4
5
6
7
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

一开始，我想到的是用动态规划的思路去解决这道题，假设dp[n] 为凑成 n 的组合数，最后发现思维上无法找到动态方程。参考了，别人的解决方案发现需要用两个变量来解决这个问题。

思路

设dp[i][j] 为用前 i 种硬币达到总金额 j 的硬币组合数。对于dp[i][j],我们可能会出现两种情况达到效果，第一种是我们没有使用第i种硬币达到j元的组合数，第二种是使用了第i种硬币达到j的组合数。

  • 没用使用第i种硬币的组合数: dp[i - 1][j]
  • 使用了第i种硬币的组合数:dp[i][j - conin[i]], j >= conin[i]

得到动态方程: dp[i][j] = dp[i-1][j] + j >= coin[i] ? dp[i][j - coin[i]] : 0

优化

其实我们并不需要记录所有的状态，我们只需要记录每增加一枚硬币带来的改变。
以 amount = 5，coins = [1,2,5] 为例。我们可以用 dp[n] 记录当前使用硬币对应钱组合数。显然dp[0] = 1是一直成立的。

当我们什么硬币都不使用的时候

n 0 1 2 3 4 5
dp[n] 1 0 0 0 0 0

使用硬币 1，只用 n >= 1 会受到影响

n 0 1 2 3 4 5
dp[n] 1 1 1 1 1 1

加上使用硬币 2，只用 n >= 2 会受到影响

n 0 1 2 3 4 5
dp[n] 1 1 2 2 3 3

加上使用硬币 5，只用 n >= 5 会受到影响

n 0 1 2 3 4 5
dp[n] 1 1 2 2 3 4

如何求dp[n]

假设我们要求加上使用第j种币时的dp[n], 当前的dp[n]可以看做是不使用第j种币得到 n 的组合数。根据前面的公式我们可以知道，我们只需要加上使用第j种币时的组合数即可，即加上dp[n - coin[j]];代码也非常精炼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/*
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    const dp = Array.from({length:amount + 1}).map(() => 0);
    dp[0] = 1;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
};