硬币划分问题

题目

链接：https://www.nowcoder.com/questionTerminal/f0605c09c4ab4b019bbfd6ef79130478?f=discussion
来源：牛客网

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述:
输入整数n.(1<=n<=100000)

输出描述:
输出组合数，答案对1e9+7取模。

思考

动态划分问题
硬币：

n = 0 或硬币只剩1时：

其他时间：

尝试

直接使用递归函数的方法进行实现，时间复杂度过高，无法通过全部实例：

n = int(input())
coins = [10,5,2,1]
k = 0

def sum_n(n, k):
    if n==0 or coins[k] == 1:
        return 1  
    sum = 0
    for i in range(n//coins[k]+1):
        sum += sum_n(n-coins[k]*i,k+1)
    return sum
print(sum_n(n,0))

题解

动态转移方法
递归过程中，所有调用函数的n，k都小于初始的n,k,在循环中按照n值从小到大，k值从小到大，计算f值。避免了使用递归方法所进行的重复计算。

n=int(input())
a=[0,1,2,5,10]
dp=[[0 for j in range(5)] for i in range(n+1)]
for i in range(0,n+1):
    dp[i][1]=1  ###只用1硬币地话永远只有一种可能
for j in range(5):
    dp[0][j]=1
for i in range(1,n+1):
    for j in range(2,5):
        if i >=a[j]:
            dp[i][j]=dp[i-a[j]][j]+dp[i][j-1]
        else:
            dp[i][j]=dp[i][j-1]
print(dp[n][4])

最后的结果应对1e9+7取模，原因：