UVa 674 - Coin Change
传送门
思路
只能想到用动态规划的方法求出当剩余找钱数为n时得到的方法数，然后不管怎么想都写不出代码。。。
可耻地参考了hcbbt的解题报告
主要就是用二维数组表示出状态，然后累加起来。
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 7489 + 100;
int dp[MAXN][5], money[] = {1, 5, 10, 25, 50};
int DFS(int target, int k)
{
int &ans = dp[target][k];
if (ans != -1)
return ans;
ans = 0;
for (int i = k; i < 5; i++)
if (target >= money[i])
ans += DFS(target - money[i], i);
return ans;
}
int main()
{
int cents, n, i, j;
memset(dp, -1, sizeof(dp));
for (i = 0; i < 5; i++)
dp[0][i] = 1;
while (~scanf("%d", ¢s))
{
int ans = DFS(cents, 0);
printf("%d\n", ans);
}
return 0;
}