思路
用给定的货币系统，求某值有多少种组合。
几乎就是个背包问题了。只不过 dp 的具体细节还要重新考虑。
我们用ways[i][j]表示用前 i 种货币去拼面值 j，不同方法有多少种。
状态转移方程：
- 不用第 i 种货币时，有
ways[i - 1][j]种。 - 必须用第 i 种货币，可以用1、2、3...个，有
ways[i][j - newCoin]种。
因此，ways[i][j] = ways[i - 1][j] + ways[i][j - newCoin]。
第二点到底是怎么回事，可以这样强行理解：大概是，既然要求必须用第 i 种货币，那我就先保证用一个，这样剩下来的部分 j - newCoin 用不用第 i 种货币就都可以，也就是ways[i][j - newCoin]了。
写的时候我可没想这么清楚，我是先按照前面完全背包问题 + O(V * N)的多重背包问题的框架，试呀试呀，最后总结出来，现在说状态转移方程纯属事后诸葛亮。
我承认写得丑，空间完全可以优化一维，循环也不用写得这么繁琐，不过这样可以和前面背包问题的框架进行对比，就看看吧……
/*
ID:
LANG: C++
TASK: money
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxV = 25, maxN = 10000;
int main(){
FILE *fin = fopen("money.in", "r");
FILE *fout = fopen("money.out", "w");
long long int ways[maxV + 1][maxN + 1];
int coins[maxV], newCoin;
int V, N;
fscanf(fin, "%d %d", &V, &N);
for(int i = 0; i < V; i ++) fscanf(fin, "%d", coins + i);
ways[0][0] = 1;
for(int i = 1; i <= N; i ++) ways[0][i] = 0;
for(int i = 1; i <= V; i ++){ //允许使用前i种硬币
newCoin = coins[i - 1];
memcpy(ways[i], ways[i - 1], sizeof(ways[i]));
for(int j = newCoin; j <= N; j ++){
ways[i][j] += ways[i][j - newCoin];
}
}
fprintf(fout, "%lld\n", ways[V][N]);
return 0;
}
由于动手前没有总结好这个方程，在内层的 j 循环我写了好久才写对，最后恍然大悟，还是和之前一样，因为每次要用数组前面元素的新值，所以当然要从前向后做。对，就是这么简单。看大家只要知道用 dp 的，好像也都是 0.000secs。
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 6084 KB]
Test 2: TEST OK [0.000 secs, 6084 KB]
Test 3: TEST OK [0.000 secs, 6084 KB]
Test 4: TEST OK [0.000 secs, 6084 KB]
Test 5: TEST OK [0.000 secs, 6080 KB]
Test 6: TEST OK [0.000 secs, 6088 KB]
Test 7: TEST OK [0.000 secs, 6080 KB]
Test 8: TEST OK [0.000 secs, 6080 KB]
Test 9: TEST OK [0.000 secs, 6088 KB]
Test 10: TEST OK [0.000 secs, 6080 KB]
Test 11: TEST OK [0.000 secs, 6084 KB]
Test 12: TEST OK [0.000 secs, 6088 KB]
Test 13: TEST OK [0.000 secs, 6088 KB]
All tests OK.
Your program ('money') produced all correct answers! This is your
submission #3 for this problem. Congratulations!
溢出？
前面有个版本，到 test11 时就崩了，这肯定已经不是我逻辑上的错误了。print 出来一看，刚到达 int 的边界就溢出了。可是我用的是 long long int。
我因为自己太蠢，带着人生导师折腾了半天。在我们都认为底层编译器的问题后，我突然发现，刚才的问题其实只是，我 fprintf 时，只知道 %d 和 %ld， 不知道要用 %lld。
对不住啦人生导师……都是我的锅……
