地址:https://leetcode.com/problems/largest-palindrome-product
题意:
给一个总额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]
转载于:https://www.cnblogs.com/hexsix/p/6412298.html
