原题链接
题意：
给五种不同面值的硬币,(50,25,10,5,1)(50, 25, 10, 5, 1)(50,25,10,5,1)
多组输入一个价值
硬币总数不超过100
问用这些硬币凑到那个价值有几种方案？
思路
枚举每种硬币，然后限制总数，最后枚举总价值。
如果没有总数限制的转移方程是f[i][j]+=f[i?1][j?v[i]]f[i][j] += f[i - 1][j - v[i]]f[i][j]+=f[i?1][j?v[i]]，递推得来的，先是都用第一种硬币能凑出哪些价格，然后第二种硬币在第一种的基础上，看不用这个硬币有多少种，那么加上这个硬币就是多少种，以此类推。简化为f[j]+=f[j?v[i]]f[j] += f[j - v[i]]f[j]+=f[j?v[i]].
但是该题有总数限制，那么我们多加一维，用第i种物品，硬币总数为j，总价值为k时，状态转移方程是f[i][j][k]+=f[i?1][j?1][k?v[i]]f[i][j][k] += f[i - 1][j - 1][k - v[i]]f[i][j][k]+=f[i?1][j?1][k?v[i]]，就是说当前物品是由不用当前这一种硬币，总数为j?1j - 1j?1时，总价值是k?v[i]k - v[i]k?v[i] 时，它有几种方案，那么加上这个物品，就有几种方案。简化为f[j][k]+=f[j?1][k?v[i]f[j][k] += f[j - 1][k - v[i]f[j][k]+=f[j?1][k?v[i]; 因为是方案数，是f[0][0]==1f[0][0] == 1f[0][0]==1递推得来的，所以要由小到大，且调用上一个的时候 f[j?1][k?v[i]]f[j - 1][k - v[i]]f[j?1][k?v[i]]有几种那么加上这个就有几种。。
详情可以借助这些图表来理解。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;const int N = 5e3 + 10;int w[5] = {
1, 5, 10, 25, 50};
int f[251][251];
int ans[300];signed main()
{
f[0][0] = 1;for (int i = 0; i < 5; i ++ ) //硬币种类 {
for (int j = 1; j <= 100; j ++ ) //硬币总数 {
for (int k = w[i]; k <= 250; k ++ ) //因为价格是由低到高递增来的，所以要正着写，是由f[0] = 1,转移过来的 {
f[j][k] += f[j - 1][k - w[i]]; }}}//先打表for (int i = 0; i <= 250; i ++ ){
for (int j = 0; j <= 100; j ++ ){
ans[i] += f[j][i];}}int n; while (scanf("%lld", &n) != EOF){
cout << ans[n] << endl;}return 0;
}