美团的一道编程题

static int getCom(int n) { if(n<0) return 0; int coins[]={1,5,10,20,50,100}; int dp[]=new int[n+1]; dp[0]=1; for(int i=0;i<coins.length;i++) { for(int j=coins[i];j<=n;j++) { dp[j] =(dp[j]+dp[j-coins[i]]); } } return dp[n]; }

没时间想，最后用了6循环暴力求解。。

动态规划，找零问题。去网上搜一下，全是

用 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

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。

回溯法

我用递归，结果虽然对但是容易暴栈

不算是动态规划吧？求组合数目，而不是最少多少张钞票啊……

leetcode 39

美团的编程题 是不是 不可以用自己的编译器

要输出所有组合还是输出组合数就行了？

很简单的dp题啊