考虑一下你有一个价值的问题N
,你需要计算有多少种方法可以N
用[1,2,5,10,20,50,100]
美元钞票来总结美元。
考虑经典的 DP 解决方案:
C = [1,2,5,10,20,50,100]
def comb(p):
if p==0:
return 1
c = 0
for x in C:
if x <= p:
c += comb(p-x)
return c
它不影响相加部分的顺序。例如,comb(4)
将产生 5 个结果:[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]
而实际上有 3 个结果([2,1,1],[1,2,1],[1,1,2]
都相同)。
计算这个问题的 DP 习语是什么?(不欢迎非优雅的解决方案,例如生成所有可能的解决方案和删除重复项)