这几天在牛客网上玩耍，发现一道题
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。
N=int(input())
dp=[1]*10001
for i in [5,10,20,50,100]:
for j in range(i,10001):
dp[j]=dp[j]+dp[j-i]#动态规划
print(dp[N])
看见一个大神的代码:
查了不少资料，把动态规划看了一下，
dp=[1]*10001
这一步是创建了一个容器，或者说一个记事本，把已经出现的情况记录下来，方便累计，其实吧，应该是用【0】来创建这个容器，但是为什么用【1】？
这是因为，在这个题里有一个1块钱，也就是说，无论你要凑多少钱都至少有全是1块钱组成的这一种可能，所以所有的面值拼凑的可能都要加一
for i in [5,10,20,50,100]:
for j in range(i,10001):
dp[j]=dp[j]+dp[j-i]#动态规划
print(dp[N])
，下面2层循环，可以看见 j 是从除了1以为的最小面值开始循环的，因为1这种情况已经考虑过了,为什么从最小面值5开始循环，因为5之前都只能有1种可能了，不用考虑
那么从金额是5开始，dp[5]记下了当金额是5的时候有多少种可能，即 全是一块的dp[j]加上有一个五块的即dp[5-5],一共有2种可能 以此往下循环dp[5],dp[6],dp[7],dp[8],dp[9]
都是两种可能，就是全1元组成或者一张5元加上一些1元组成。从dp[10]开始不一样了，dp[10] = dp[10]+dp[10-5] 结果是3 就是全用1元组合dp[10] 加上包含一张5元的情况下另外2种可能，就是5块，5块，和5块，5个一块这2种组合
加在一起用了3种方法，记录下来，然后继续，每够一次五块，就会多出2种方法，