面试题 08.11. 硬币，动态规划

题目描述

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

解题思路

思路：dp[j][i] = (dp[j-1][i] + dp[j][i- coin[j]])
其中dp[j-1][i]表示使用j-1个硬币，组成i时可以得到的方法数。

也可以简化成下面的形式：
dp[i] = dp[i] + dp[i-coin[j]]
一种迭代的方式，注意此时等式右边的值是上一次的结果。

代码

Code

class Solution:
    def waysToChange(self, n: int) -> int:
        dp = []
        for i in range(n+1):
            dp.append(1)
        coin = [1,5,10,25]
        for c in coin[1:]:
            for i in range(1, n+1):
                if i >= c:
                   dp[i] = (dp[i] + dp[i-c])%1000000007
        return dp[n]