uva674Coin Change

题意：手中的硬币币值有1,5,10,25,50共5种，给定一个面值n，问把n兑换成硬币的方案总数是多少。

分析：先打表，再输入输出。动态规划的简单题目，设dp[i]表示面值为i的情况下能兑换的种类，那么dp[i]=sigma(dp[i-v[j]]), j=0..4, v[j]={1,5,10,25,50};也就是，如果i大于v[j]，说明能够用dp[i-v[j]]的方案再加上一枚面值为v[j]的硬币作为面值i的方案，不过这只是方案中硬币的数量多了一枚，题目中只是问方案数量，那么此时两者在方案数量上等价，那么方案总数上加上这一种情况就可以了。

代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define DEBUG
const int MAXN = 7500;
int dp[MAXN];
int main(){
#ifndef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    int i, j;
    int v[5] = {1, 5, 10, 25, 50};
    memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(i=0; i<5; i++)
        for(j=1; j<MAXN; j++)
            if(j>=v[i]) dp[j]+=dp[j-v[i]];
    int n;
    while(scanf("%d", &n)!=EOF) printf("%d\n", dp[n]);
    return 0;
}