You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Input: amount = 10, coins = [10]
Output: 1
Note:
You can assume that:
这道题是找组合方案数,而不是排列数。因此,如果使用 【DP、BFS】322. Coin Change 这道题中的 BFS 方法,貌似不可行。
但是,可以使用动态规划的思想去解决。创建一个大小为 dp1+amount 的数组,其中 dpj 表示总额为 j 的组合方案数。最后,dp-1 就是答案。
关键是如何找到状态转移方程。因为是要找组合方案数,所以对于 (1 2)、(2 1) 这种的其实是一样的,所以我们的外层循环应该是 coin,即 for coin in coins
**(这样就避免出现排列问题)。**那么,内层循环 j 就是用 当前的 coin 去更新这个 dp 数组中的方案数。
转移方程式可以想到:dpj = dp[j-coinsi],但是因为外层循环的每个 coinsi 都可能更新这个 dpj,因此最终的转移方程式应该为:
dp[j] = ∑ dp[j-coins[i]]
表示总额为 j 时的方案数 = 总额为 j-coinsi 的方案数的加和。∑ 次数等于外层循环次数。
记得初始化 dp0 = 1,表示总额为 0 时方案数为 1。其他位置的 dpj 初始化为 0。
时间复杂度 O(c*n),空间复杂度 O(n),其中 c 为硬币种类数,n 为总额 amount。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount
for coin in coins:
for j in range(coin, amount+1):
dp[j] += dp[j-coin] # dp[j] 是所有 coins 累加的结果
return dp[-1]
print(Solution().change([2,1], 3)) # 2 (111,12)
如果这道题是求不同的排列数呢?比如 (1 2)和 (2 1)是不同的情况。那么该怎么去做?
其实,这个问题是 Leetcode 的另一道题: