动态规划 HDU-2069 Coin Change

题目链接：[ HDU - 2069 ]

题目大意

有五种面值的硬币，面值分别为v1, v2, ..., vn, 数量无限。输入一个数，求这个价值所有可能的硬币组合

思路

定义dp[i][j], 表示价格为i时用j枚硬币的方案数量

dp[i][j] = dp[i][j] + dp[1 - type[k]][j - 1]

题解代码

#include<bits/stdc++.h>
using namespace std;

const int coin = 101;
const int money = 251;
int dp[money][coin];
int ans[money];
int type[5] = {1, 5, 10, 25, 50};

void solve(void)
{
    dp[0][0] = 1;
    for (int i = 0; i < 5; i++)
        for (int j = 1; j < coin; j++)
            for (int k = type[i]; k < money; k++)
                dp[k][j] += dp[k - type[i]][j - 1];
}

int main(void)
{
    int s;
    memset(dp, 0, sizeof(dp));
    memset(ans, 0, sizeof(ans));
    solve();
    for (int i = 0; i < money; i++)
        for (int j = 0; j < coin; j++)
            ans[i] += dp[i][j];

    while (cin >> s)
        cout << ans[s] << endl;

    return 0;
}