题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
1 | 输入: amount = 5, coins = [1, 2, 5] |
示例 2:
1 | 输入: amount = 3, coins = [2] |
示例 3:
1 | 输入: amount = 10, coins = [10] |
题解
完全背包问题框架
我们可以把这个问题转化为背包问题的描述形式:
有一个背包,最大容量为 amount
,有一系列物品 coins
,每个物品的重量为 coins[i]
,每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?
第一步要明确两点,「状态」和「选择」。
状态有两个,就是「背包的容量」和「可选择的物品」,选择就是「装进背包」或者「不装进背包」嘛,背包问题的套路都是这样。
明白了状态和选择,动态规划问题基本上就解决了,只要往这个框架套就完事儿了:
1 | for 状态1 in 状态1的所有取值: |
第二步要明确 dp
数组的定义。
首先看看刚才找到的「状态」,有两个,也就是说我们需要一个二维 dp
数组。
dp[i][j]
的定义如下:
若只使用前 i
个物品,当背包容量为 j
时,有 dp[i][j]
种方法可以装满背包。
换句话说,翻译回我们题目的意思就是:
若只使用 coins
中的前 i
个硬币的面值,若想凑出金额 j
,有 dp[i][j]
种凑法。
经过以上的定义,可以得到:
base case 为 dp[0][..] = 0, dp[..][0] = 1
。因为如果不使用任何硬币面值,就无法凑出任何金额;如果凑出的目标金额为 0,那么“无为而治”就是唯一的一种凑法。
我们最终想得到的答案就是 dp[N][amount]
,其中 N
为 coins
数组的大小。
第三步,根据「选择」,思考状态转移的逻辑。
注意,我们这个问题的特殊点在于物品的数量是无限的,所以这里和之前写的背包问题文章有所不同。
如果你不把这第 i
个物品装入背包,也就是说你不使用 coins[i]
这个面值的硬币,那么凑出面额 j
的方法数 dp[i][j]
应该等于 dp[i-1][j]
,继承之前的结果。
如果你把这第 i
个物品装入了背包,也就是说你使用 coins[i]
这个面值的硬币,那么 dp[i][j]
应该等于 dp[i][j-coins[i-1]]
。
首先由于 i
是从 1 开始的,所以 coins
的索引是 i-1
时表示第 i
个硬币的面值。
dp[i][j-coins[i-1]]
也不难理解,如果你决定使用这个面值的硬币,那么就应该关注如何凑出金额 j - coins[i-1]
。
比如说,你想用面值为 2 的硬币凑出金额 5,那么如果你知道了凑出金额 3 的方法,再加上一枚面额为 2 的硬币,不就可以凑出 5 了嘛。
综上就是两种选择,而我们想求的 dp[i][j]
是「共有多少种凑法」,所以 dp[i][j]
的值应该是以上两种选择的结果之和:
1 | public int change(int amount, int[] coins) { |
状态压缩, 优化空间复杂度
1 | public int change(int amount, int[] coins) { |