地址:
题意:
- 给一个总额amount,
- 给若干个面额不同的硬币的集合coins,
- 问组成总额的方案数.
题解:
- 简单DP.
- dp[i]表示总额为i时的方案数.
- 转移方程: dp[i] = Σdp[i - coins[j]]; 表示 总额为i时的方案数 = 总额为i-coins[j]的方案数的加和.
- 记得初始化dp[0] = 1; 表示总额为0时方案数为1.
代码:
- 1 class Solution(object):
- 2 def change(self, amount, coins):
- 3 """
- 4 :type amount: int
- 5 :type coins: List[int]
- 6 :rtype: int
- 7 """
- 8 size = len(coins)
- 9 dp = [1] + [0] * amount
- 10 for i in range(size):
- 11 for j in range(amount):
- 12 if j + coins[i] <= amount:
- 13 dp[j + coins[i]] += dp[j]
- 14 return dp[-1]
来源: http://www.bubuko.com/infodetail-1949180.html