HDU-2069-Coin Change

链接：https://vjudge.net/problem/HDU-2069

题意：

给你面值有1，5，10，25，50的币种，然后随意输入一个钱的数目，问用这些面值刚好凑成这个钱的方法有多少个（最多100个硬币）

思路：

dp，二位数组，dp[i][j]。表示i值用j个硬币有几种方法。

好像这题有0的输入。。真坑

代码：

#include <iostream>
#include <memory.h>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <queue>
#include <string>
#include <stack>

using namespace std;

typedef long long LL;

const int MAXN = 7500 + 10;

int dp[MAXN][110];
int value[10] = {0, 1, 5, 10, 25, 50};

void Solve()
{
    dp[0][0] = 1;
    for (int i = 1;i <= 5;i++)
    {
        for (int v = value[i];v <= 7500;v++)
        {
            for (int j = 1;j <= 100;j++)
                dp[v][j] += dp[v - value[i]][j - 1];
        }
    }
}

int main()
{
    int n;
    Solve();
    while (~scanf("%d", &n))
    {
        int res = 0;
        for (int i = 0;i <= 100;i++)
            res += dp[n][i];
        printf("%d\n", res);
    }

    return 0;
}