面试题 08.11. 硬币

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

示例1:

输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：

注意:
你可以假设：

• 0 <= n (总金额) <= 1000000

Python 解答：
1.动态规划，由于j只和前一行有关，可以用滚动数组优化。

class Solution:
    def waysToChange(self, n: int) -> int:
        arr = [1, 5, 10, 25]
        matrix = [[0 for i in range(n+1)] for j in range(len(arr))]
        for i in range(n+1):
            matrix[0][i] = 1
        for j in range(len(arr)):
            matrix[j][1] = 1
        for j in range(1, len(arr)):
            for i in range(2, n+1):
                if i-arr[j] > 0:
                    matrix[j][i] = (matrix[j-1][i] + matrix[j][i-arr[j]])%1000000007
                elif i-arr[j] == 0:
                    matrix[j][i] = matrix[j-1][i] + 1
                else:
                    matrix[j][i] = matrix[j-1][i]
        return matrix[len(arr)-1][n]

2.只有4种可以通过数学展开

3.回溯法，不过会超时

class Solution:
    def waysToChange(self, n: int) -> int:
        count = 0
        arr = [25, 10, 5, 1]
        def dfs(n, pre):
            if n < 0:
                return
            elif 0 <= n < 5:
                nonlocal count
                count += 1
                return
            for item in arr:
                if item <= pre:
                    n -= item
                    dfs(n, item)
                    n += item
        dfs(n, 30)
        return count%1000000007