当前位置:网站首页>LeetCode 322. Change exchange (dynamic planning)
LeetCode 322. Change exchange (dynamic planning)
2022-07-06 01:25:00 【zjsru_ Beginner】
Subject portal :322. Change for
Topic details :
Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .
Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .
You can think of the number of coins of each kind as infinite .
Example 1:
Input :coins = [1, 2, 5], amount = 11
Output :3
explain :11 = 5 + 5 + 1
Example 2:Input :coins = [2], amount = 3
Output :-1
Example 3:Input :coins = [1], amount = 0
Output :0Tips :
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
Topic analysis :
After a simple analysis, it is found that it is very similar to a complete backpack , The number of coins is infinite , But the total amount ( The capacity of the backpack ) It is the same. , We are required to use the least number of coins , So we use dynamic programming to solve this problem .
First determine dp Array , The array stores the minimum number of coins required for the total amount we give , The subscript of the array is the total amount given , So we should finally return the array with the subscript amount Value , namely dp [amount];
Next, determine the recurrence equation :
Take an example to analyze :
Input :coins = [1, 2, 5], amount = 11
Output :3
The total amount collected 11 The minimum number of coins required is dp[11 - 5] + 1( Take the denomination as 5 The coin of , Number of coins +1), and 11-5 by 6, The total amount is 6 The minimum number of coins required is dp[6 - 5] + 1( Then take the denomination as 5 The coin of , Number of coins +1), And so on until the amount is 0. We found that 6 Also can be 3 The denomination is 2 Coins of , But at this time, the number of coins taken is greater than that used The denomination is 5 The coin plus the denomination is 1 The coin of 2 gold , Therefore, we should constantly select the smallest one to ensure the total amount The least number of coins . So the recurrence equation is dp[ i ]=min(dp[ i - coins[ j ] ] + 1,dp[ i ])(i For the amount that needs to be scraped up )
dp[ 0 ]=0, Other values are initialized to the maximum value to avoid being overwritten in the comparison .
Code (c++):
class Solution {
public:
int max=999999999;
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,max);
dp[0]=0;// The total amount is 0 You don't need a coin
int length=coins.size();
for(int i=1;i<=amount;i++)// From the amount 1 Start to the requested amount amount
{
for(int j=0;j<length;j++)
{
if(coins[j]<=i) The denomination of the coin is less than the current amount
dp[i]=min(dp[i-coins[j]]+1,dp[i]);
}
}
if(dp[amount]==max)
return -1;
else
return dp[amount];
}
};
Computer 204 zjr
边栏推荐
- Interview must brush algorithm top101 backtracking article top34
- Docker compose配置MySQL并实现远程连接
- [机缘参悟-39]:鬼谷子-第五飞箝篇 - 警示之二:赞美的六种类型,谨防享受赞美快感如同鱼儿享受诱饵。
- False breakthroughs in the trend of London Silver
- Obstacle detection
- ADS-NPU芯片架构设计的五大挑战
- Xunrui CMS plug-in automatically collects fake original free plug-ins
- [the most complete in the whole network] |mysql explain full interpretation
- WGet: command line download tool
- In the era of industrial Internet, we will achieve enough development by relying on large industrial categories
猜你喜欢
How to see the K-line chart of gold price trend?
现货白银的一般操作方法
Unity | 实现面部驱动的两种方式
IP storage and query in MySQL
282. Stone consolidation (interval DP)
Kotlin basics 1
[机缘参悟-39]:鬼谷子-第五飞箝篇 - 警示之二:赞美的六种类型,谨防享受赞美快感如同鱼儿享受诱饵。
WordPress collection plug-in automatically collects fake original free plug-ins
Mathematical modeling learning from scratch (2): Tools
A Cooperative Approach to Particle Swarm Optimization
随机推荐
XSS learning XSS lab problem solution
MYSQL---查询成绩为前5名的学生
Alibaba-Canal使用详解(排坑版)_MySQL与ES数据同步
[pat (basic level) practice] - [simple mathematics] 1062 simplest fraction
Kotlin basics 1
Test de vulnérabilité de téléchargement de fichiers basé sur dvwa
leetcode刷题_平方数之和
晶振是如何起振的?
IP storage and query in MySQL
What is weak reference? What are the weak reference data types in ES6? What are weak references in JS?
在产业互联网时代,将会凭借大的产业范畴,实现足够多的发展
ctf. Show PHP feature (89~110)
3D vision - 4 Getting started with gesture recognition - using mediapipe includes single frame and real time video
Crawler request module
Xunrui CMS plug-in automatically collects fake original free plug-ins
Blue Bridge Cup embedded stm32g431 - the real topic and code of the eighth provincial competition
Idea sets the default line break for global newly created files
servlet(1)
Electrical data | IEEE118 (including wind and solar energy)
朝招金安全吗 会不会亏损本金