UVA 674 Coin Change 硬币转换（完全背包，常规）

题意:有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代码

巴特西

UVA 674 Coin Change 硬币转换（完全背包，常规）

最新文章

热门文章