与 HDU 1028 相似的题目。
方法一：完全背包。
限制条件：硬币总值不超过 n。
目标：求出组合种数。
令 dp[ i ][ j ] == x 表示用前 i 种硬币组合价值为 j 的钱共 x 种方法。
状态转移方程：dp[ i ][ j ] = dp[ i - 1][ j ] + dp[ i ][ j - v[ i ] ] ；
方程解释：用前 i 种硬币组合出钱 j 的方法数 = 前 i - 1 种硬币组合出钱 j 的方法数（不用第 i 种硬币）+ 至少用一枚第 i 种硬币的方法数。
滚动数组实现，i 的这一维便可省去。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int n,dp[maxn];
void init()
{
memset(dp,,sizeof(dp));
dp[] = ;
for(int i = ; i <= ; ++i)
for(int j = i; j < maxn; ++j)
dp[j] += dp[j-i];
}
int main()
{
init();
while(~scanf("%d",&n))
printf("%d\n",dp[n]);
return ;
}
方法二：母函数。
用( 1 + x^k + x^(k*2) + x^(k*3) + ...) 表示参与组成的价值为 k 的硬币，1 表示硬币 k 个数为 0，每项前面的系数表示组成钱 k ( x 的次方数) 的方法数。
比如现有 1 分，3 分，6 分的硬币各 1 枚，便可得到：
( 1 + x^1 ) * ( 1 + x^3 ) * ( 1 + x^6 ) = 1 + x^1 + x^3 + x^4 + x^6 + x^7 + x^9 + x^10；
这表示用 1 分，3 分，6 分的硬币各 1 枚可以组合出钱数为 0，1，3，4，6，7，9，10 的方法各 1 种。
若是 1 分，3 分，6 分的硬币各 2 枚的话，就可得到：
( 1 + x^1 + x^2 ) * ( 1 + x^3 + x^6 ) * ( 1 + x^6 + x^12 ) =
1 + x^1 + x^2 + x^3 + x^4 + x^5 + 2*x^6 + 2*x^7 + 2*x^8 + x^9 + x^10 + x^11 + 2*x^12 + 2*x^13 + 2*x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + x^20
这表示用 1 分，3 分，6 分的硬币各 2 枚可以组合出
钱数为 0 的方法 1 种，钱数为 1 的方法 1 种，钱数为 2 的方法 1 种，钱数为 3 的方法 1 种，钱数为 4 的方法 1 种，
钱数为 5 的方法 1 种，钱数为 6 的方法 2 种，钱数为 7 的方法 2 种，钱数为 8 的方法 2 种，钱数为 9 的方法 1 种，
钱数为 10 的方法 1 种，钱数为 11 的方法 1 种，钱数为 12 的方法 2 种，钱数为 13 的方法 2 种，钱数为 14 的方法 2 种，
钱数为 15 的方法 1 种，钱数为 16 的方法 1 种，钱数为 17 的方法 1 种，钱数为 18 的方法 1 种，钱数为 19 的方法 1 种，
钱数为 20 的方法 1 种。
（神奇.......要了解更多关于母函数的问题请点这里）
手工模拟多项式展开，代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int n,ans[maxn],tans[maxn];
void init()
{
for(int i = ; i < maxn; ++i)
{
ans[i] = ;
tans[i] = ;
}
for(int i = ; i <= ; ++i)
{
for(int j = ; j < maxn; ++j)
for(int k = ; j+k < maxn; k+=i)
tans[j+k]+=ans[j];
for(int j = ; j < maxn; ++j)
{
ans[j] = tans[j];
tans[j] = ;
}
}
}
int main()
{
init();
while(~scanf("%d",&n))
printf("%d\n",ans[n]);
return ;
}
向这些博客的作者致谢：
https://www.cnblogs.com/13224ACMer/p/4671551.html
https://blog.****.net/u013480600/article/details/40477769