题意:有5种硬币，个数无限的，组成n元的不同方案有多少种?
思路:常规完全背包。重点在dp[0]=1，dp[j]中记录的是组成 j 元的方案数。状态转移方程dp[j+coin[i]]+=dp[j]。
#include <bits/stdc++.h>
using namespace std;
int coin[]={, , , , };
int dp[], n; int cal()
{
if(!n) return ;
memset(dp,,sizeof(dp));
dp[]=;
for(int i=; i<; i++)
for(int j=; j+coin[i]<=n; j++)
dp[j+coin[i]]+=dp[j];
return dp[n];
}
int main() {
//freopen("input.txt", "r", stdin);
while(~scanf("%d",&n))
printf("%d\n",cal()); return ;
}
AC代码