文章目錄

• • 循環(huán)解法

各種湊零錢問題，非常有趣

背包問題之零錢兌換
(知乎上禁了，pdf上還有)
Leetcode 322 Coin Change
給定一系列的coins，和一個(gè)target，現(xiàn)在需要使用這些coins組成target，問最少需要的硬幣數(shù)是多少？

示例1：
輸入：Coins = [1,2,5], target = 11
輸出：3

示例2：
輸入：Coins = [2], target = 3
輸出：-1
時(shí)間緊任務(wù)重就不改輸入了，這個(gè)是示例一的，主要看思路【補(bǔ)救】把

Q：如果1，2，3，5，湊某個(gè)數(shù)n要x個(gè)，完了n+1正好可以用2換1，或者3換2，這不就是x了嗎，不對(duì)了嗎？

#include<bits/stdc++.h> using namespace std; int record[10000]={0}; int coins[3]={1,2,5}; int coinslenth=3; int dp(int n){if(n==0){return 0;}if(n<0){return -1;}if(record[n]){return record[n];}int res=1000000;for(int i=0;i<coinslenth;i++){int j=dp(n-coins[i]);if(j<0){ ///這里寫法不錯(cuò)，是當(dāng)無解的時(shí)候才可以，用一個(gè)數(shù)存也可以減少計(jì)算量continue;}res=min(res,j+1);} record[n]=res; if(res!=1000000)///還有這句算是補(bǔ)救，讓他判斷沒更新res的情況(全不行) return res; else{return -1; } } int main() {cout<<dp(11);return 0; }

---

2020.9.11解法
///不管怎么樣，邊界一定要好好返回

#include<bits/stdc++.h> using namespace std; int record[10000]={0}; int coins[3]={1,2,5}; int coinslenth=3; int dp(int n){if(n<0)return -1;if(n==0)return 0;///不管怎么樣，邊界一定要好好返回if(record[n]!=0)return record[n];int res=100000;int dpp;for(int i=0;i<3;i++){dpp=dp(n-coins[i]);if(dpp==-1){continue;}res=min(res,dpp+1);}if(res==100000){ record[n]=-1 ;return -1;}record[n]=res; return res; } int main() {cout<<dp(11);return 0; }

循環(huán)解法

int record[10000]={12};///初始化有問題，引以為戒！！！！！

#include<bits/stdc++.h> using namespace std; int record[10000]={12};///初始化有問題，引以為戒！！！！！ int coins[3]= {1,2,5}; int coinslenth=3; int main() {for(int i=0;i<10000;i++){record[i]=12;}int target=11;record[0]=0;for(int n=0; n<=target+1; n++) ///n指當(dāng)前所求數(shù)，i用來遍歷面額{for(int i=0; i<coinslenth; i++){if(n-coins[i]<0){continue;}record[n]=min(record[n],record[n-coins[i]]+1);}}cout<<record[11];return 0; }

總結(jié)

以上是生活随笔為你收集整理的凑零钱问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。