dp[m][n] 是加和为 n 而且最大的钞票是 m
的组合数量。
初值: dp[m][0] = 1 for m in
1,10,20,30,50,100
状态: dp[m][k] = \sum_{i <= m}
dp[i][k-m] for k in 1:n
结果: N = sum_m dp[m][n]
这样算出来的是所有递增的排列数量,也就是组合数量。感觉容易超整数范围,看情况用 long long。
用 Python 写了个代码,对 DP 有少量修改:
初值: dp[m][m] = 1 for m in
1,10,20,30,50,100
状态: dp[m][k] = \sum_{i <=
m} dp[i][k-m] for k in 1:n if k > m
结果: N = sum_m dp[m][n]
代码:
from sys import stdin
N = int(stdin.readline())
C = [1, 10, 20, 30, 50, 100]
C.sort()
dp = dict([(c,[0]*(N+1)) for c in C])
for k in xrange(1,N+1):
for c in C:
if k == c:
dp[c][c] = 1
elif k > c:
dp[c][k] = sum([dp[i][k-c] for i in C if i <= c])
CS = sum([dp[c][N] for c in C])
print CS