---

---

一、零錢兌換-LeetCode 322

Leecode鏈接: leetcode 322
文章鏈接: 代碼隨想錄
視頻鏈接: B站

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

示例1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

思路

本題是一個完全背包，物品數量不限，設dp[j]，數組含義表示容量為j時，滿足該容量下的最小金幣數目。遞推公式為：dp[j] = min(dp[j],dp[j - coins[i]]+1);因為是完全背包所以循環遵循背包容量由小到大。

實現代碼

//cpp
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);dp[0] = 0;for(int i = 0;i<coins.size();i++){for(int j = coins[i];j<=amount;j++){if(dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j],dp[j-coins[i]]+1);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}
};

問題

初始化dp數組時，不知道遵循什么規則。

總結

題目是完全背包類型的題目，不過不再是尋求取最大值，而是取最小值。此外，遍歷時，遇到INT_MAX也會直接跳過，表示上一個背包容量沒有保存數據。換句話就是表示沒有找到滿足該容量的硬幣數量，那么后續一定找不到對應的硬幣數量，因為動態規劃本質就是需要前面的數據來推出本次循環容量對應數據，所以直接跳過。

---

二、完全平方數-LeetCode 279

Leecode鏈接: LeetCode 279
文章鏈接: 代碼隨想錄
視頻鏈接: B站

給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。

完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

示例1：

輸入：n = 12
輸出：3 
解釋：12 = 4 + 4 + 4

思路

定義數組dp[j]，數組含義為：滿足容量j時，所需要的最少的完全平方數的個數。遞推公式為：dp[j] = min(dp[j],dp[j - i*i]+1);初始化與遍歷的規范與上一題一樣。

實現代碼

//cpp
class Solution {
public:int numSquares(int n) {vector<int>dp(n+1,INT_MAX);dp[0] = 0;for(int i = 1;i<=sqrt(n);i++){for(int j = i*i;j<=n;j++){dp[j] = min(dp[j],dp[j - i*i]+1);}}return dp[n];}
};

問題

無。

總結

題目是完全背包很好的一個例題，唯一有特點的地方在于：物品是從1開始的各個數的平方，不再由題目給出具體的數組。