题意：给一个钱数n，有5种硬币，求有多少种组合方法。
思路：记忆化搜索。
很容易想到状态转移方程：f[i] = sum(f[i-coin[j]),但是有一个问题，一维的无法解决，因为会有重复，比如
如f[11] = f[10]+f[6]+f[1] ，
所以用二维表示，避免重复。
//0 KB 42 ms
#include <cstdio>
#include <cstring>
const int M = 7500;
using namespace std;
int coin[5] = {50,25,10,5,1};
int f[5][M];
int dp(int u,int num)
{
if (num == 0)
return 1;
if (f[u][num])
return f[u][num];
for (int i = u; i < 5; i ++)
if (num >= coin[i])
f[u][num] += dp(i,num-coin[i]);
return f[u][num];
}
int main()
{
int n;
memset (f,0,sizeof(f));
while (~scanf ("%d",&n))
printf ("%d\n",dp(0,n));
return 0;
}