寒假。。数不清第几天了，反正继续加油。今天开始dp（树得啃一会了）

题目概述

链接：https://vjudge.net/problem/HDU-2069
描述：大致意思是说，有1，5，10，25，50这几种面额的硬币，输入一个数值，输出组成这个数值可以选用硬币的方案，且硬币总数不能超过100。

思路分析

这道应该是一道dp基础经典问题。这道题的难点在于：要用什么来记录状态、怎么描述一个状态。参考黑书的方案，我用的是一个二维数组来记录状态。
其中，i表示要表示的数，j表示所用的硬币数量，表格内填的数字就是用j硬币表示i金额的方案数。
现在这样考虑：用1个硬币表示1分钱，有1种方案，所以（1,1）=1((i,j)),2个硬币表示2分钱有(2,2)=1种方案……以此类推，得到：
继续考虑：
当用5分钱硬币的时候，表示的数额肯定是5分起步。5分需要1个硬币，6分需要2个硬币……，得到：
根据上面的规律，我们可以想到状态转移方程：
dp[i][j]+=dp[i-type[k]][j-1]
注：因为可能存在硬币数和表示的面额数相同，但方案不同的情况，所以需要用+=，而不是直接赋值。
这样就可以得到整一个完整的表，其中，每一列的和就表示组成这个面额的方案数。接下来，再打一个ans表，输出就能完成。

完整代码

#include <iostream>
using namespace std;
const int maxcoin=101;
const int maxval=251;
int dp[maxval][maxcoin]={0};
int type[]={1,5,10,25,50};
void solve(){
	for(int i=0;i<5;i++)//硬币类型 
	{
		for(int j=1;j<maxcoin;j++)//硬币数量 
		{
			for(int k=type[i];k<maxval;k++)//实现数额 
			{
				dp[k][j]+=dp[k-type[i]][j-1]; 
			}
		}
	}
}



int main()
{
	dp[0][0]=1;
	int s;
	int ans[maxval]={0};
	solve();
	for(int i=0;i<maxval;i++)
	{
		for(int j=0;j<maxcoin;j++)
		{
			ans[i]+=dp[i][j];
		}
	}
	while(cin>>s)
	{
		cout<<ans[s]<<endl;
	}
	return 0;
}