HOJ 2069 Coin Change（动态规划）

题目意思：
有5种硬币， 币值分别是 1, 5, 10, 25, 50。
题目给出 数n，求出由这5种硬币组成币值n， 有多少种选法。

本题要点：
1、状态表示：
dp[i][j]表示用j个硬币实现i金额的方案数
2、状态转移方程：
for(int k = type[i]; k < MONEY; ++k) //5种硬币
{
dp[k][j] += dp[k - type[i]][j - 1];
}

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MONEY = 251, COIN = 101;
int dp[MONEY][COIN];	//dp[i][j]表示用j个硬币实现i金额的方案数
int s;
int type[6] = {
    0, 1, 5, 10, 25, 50};
int ans[MONEY];void solve()
{
    memset(dp, 0, sizeof dp);dp[0][0] = 1;for(int i = 1; i <= 5; ++i){
    for(int j = 1; j < COIN; ++j){
    for(int k = type[i]; k < MONEY; ++k)	//5种硬币{
    dp[k][j] += dp[k - type[i]][j - 1];}}}
}int main()
{
    solve();	for(int i = 0; i < MONEY; ++i)for(int j = 0; j < COIN; ++j){
    ans[i] += dp[i][j];	}while(scanf("%d", &s) != EOF){
    printf("%d\n", ans[s]);}return 0;
}/* 11 26 *//* 4 13 */