题目链接：https://vjudge.net/contest/59424#problem/A
题目大意：
有5种硬币， 面值分别为1、5、10、25、50，现在给出金额，问可以用多少种方式组成该面值。
解题思路：
首先我们可以想到，用这些硬币组成11有多少种．
就是组成10的种数，加上组成６的种数，加上组成１的种数，因为这些面值都是加上一枚硬币就得到11了.
然后我们又能继续去求1组成10的种数,那么明显就是9,5,0的组成数的和.
需要注意的是1+5自底向上的方法，需要注意的是1+5和5+1是一种的，所以要处理一下，从小往大排就不会错了。
这道题我还不是很懂，以后再看看。 转载于>>>
记忆化搜索：很白痴的算法，直接交给下一层去算，算完记录下来以免之后重复算。
#include <cstdio>
#include <cstring>
const int MAXN = ;
const int coin[] = {, , , , };
int n;
long long dp[MAXN][]; long long solve(int i, int s) {
if (dp[s][i] != -)
return dp[s][i];
dp[s][i] = ;
for (int j = i; j < && s >= coin[j]; j++)
dp[s][i] += solve(j, s - coin[j]);
return dp[s][i];
} int main() {
memset(dp, -, sizeof(dp));
for (int i = ; i < ; i++)
dp[][i] = ;
while (scanf("%d", &n) != EOF)
printf("%lld\n", solve(, n));
return ;
}
递推：自底向上的方法，需要注意的是1+5和5+1是一种的，所以要处理一下，从小往大排就不会错了。
#include <cstdio>
const int MAXN = ;
int n, coin[] = {, , , , };
long long dp[MAXN] = {}; int main() {
for (int i = ; i < ; i++)
for (int j = ; j < MAXN - ; j++)
dp[j + coin[i]] += dp[j]; while (scanf("%d", &n) != EOF)
printf("%lld\n", dp[n]);
return ;
}
2018-04-30