这题开始是以为知道大概思路的，但就是很难实现。想了好久实在忍不住了搜了博客

发现是DP/背包问题，对这两种都没什么了解，也就很正常了。

DP思路是通过求出 每次输入的 所需硬币数 （如5可能需要1个硬币，即一个5，或者5个硬币，五个1）的方案数量，通过累加所有硬币数的所有方案之和得到结果。

难点是如何推出状态转移方程，我们如何通过之前的结果推导出之后的结果才是关键。

本题的特点是，由于硬币值越小，可以满足的输入就越多，故我们从最大的开始。

所以先int a[5] = {50, 25, 10, 5, 1};

故我们每次累加从a[i]开始，刚开始尽可能有硬币值大的组合，到最后就是硬币值较小的组合。

例如我们刚开始时所有的可能都为0，dp[0][0] = 1; 然后从1种硬币组合，若之后的组合都不能只用一个硬币，则所累加的全部为0. 如11 = 10 * 1 + 1 * 1都至少需要两个，11 = 5 * 2 + 1 * 1， 11 = 5 * 1 + 1 * 6， 11 = 1 * 11.

关于dp[0][0] = 1，由此开始累加，dp[0][0]实际上无意义

贴个代码

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll dp[255][105];
int a[5] = {50, 25, 10, 5, 1};
int main()
{
	int n;
	
	while(~scanf("%d", &n)){
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for(int i = 0; i < 5; i++)
			for(int j = 1; j <= 100; j++)
				for(int k = a[i]; k <= n; k++)//这是需要求的价值 
					dp[k][j] = dp[k][j] + dp[k-a[i]][j-1]; //循环求得至n的所有组合结果，从最大硬币开始。 
		int sum = 0;
		for(int i = 0; i <= 100; i++)
			sum = sum + dp[n][i];
		printf("%d\n", sum);
	}
	return 0;
}