这道题的意思是有5中硬币1 5 10 25 50问有几种方法可以组成n。。dp[i][j]为前i中组成j的方案数则 dp[i][j] = dp[i-1][j] + dp[i][j-v[i]]..可以使用滚动数组优化。。代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int wu[6] = {0, 1, 5, 10, 25, 50}; int f[8000 + 100]; int main() { memset(f, 0, sizeof(f)); f[0] = 1; for(int i=1; i<=5; i++) for(int j=0; j<=8000; j++) //注意方向 { if(j >= wu[i]) f[j] = f[j] + f[j-wu[i]]; } int n; while(scanf("%d", &n) == 1) { printf("%d\n", f[n]); } return 0; }
原文：http://www.cnblogs.com/xingxing1024/p/5007864.html