代碼：（完全背包）

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int dp[32775]; int main() {int i,j,n;memset(dp,0,sizeof(dp));dp[0]=1;for(i=1;i<=3;i++){for(j=i;j<=32775;j++)//j代表的是錢數，不能小于當前價值為i的硬幣{dp[j]+=dp[j-i];
　　　　　　　//dp[i][j]=dp[i-1][j]+dp[i][j-i];//表示用前i種硬幣構造j美分的總方法數}}while(scanf("%d",&n)==1){printf("%d\n",dp[n]);}return 0; }

其他解法詳見：http://blog.sina.com.cn/s/blog_91e2390c01014b1u.html

?

假如3的個數為i，則剩余的需兌換的錢有n-3*i，剩余的對2來說，有可能有0，1，2...(n-3*i)/2；即有i個3的情況有 (n-3*i)/2+1個（2從0開始） ；
3和2的個數確定了，1的個數也確定；

#include<stdio.h> int main() {int n;while(~scanf("%d",&n)){long long sum=0;for(int i=0 ; i<=n/3 ; i++)//枚舉3的可能個數，有n/3種可能 sum+=(n-3*i)/2+1;//+1是因為，每一種換法可以直接全部換為1元硬幣 printf("%lld\n",sum);}return 0; }

?

轉載于:https://www.cnblogs.com/LJHAHA/p/10466581.html

總結

以上是生活随笔為你收集整理的钱币兑换问题 （完全背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。