这是一道比较简单的一维dp问题。给一个数字n，然后再给m种不同面值的硬币，求这个数字能被这些硬币以多少种组合方式组合起来。
状态就选择成 ：
设为n被组合起来的方式。
我们手上有m个硬币，设为
所以代码如下:
def getWays(n, c):
dp = [1] + [0] * n
for i in range(len(c)):
for j in range(c[i],n+1):
dp[j] += dp[j - c[i]]
return dp[-1]
网友评论