Leetcode?322. 零錢兌換
題目鏈接：322 零錢兌換
題干：給你一個整數數組?
coins?，表示不同面額的硬幣；以及一個整數?amount?，表示總金額。計算并返回可以湊成總金額所需的?最少的硬幣個數?。如果沒有任何一種硬幣組合能組成總金額，返回?-1?。你可以認為每種硬幣的數量是無限的。
1 <= coins.length <= 121 <= coins[i] <= 231?- 10 <= amount <= 104
思考：動態規劃。題目中說每種硬幣的數量是無限的，可以看出是典型的完全背包問題。
- 確定dp數組以及下標的含義
dp[j]：從coins中任取硬幣，達到總金額為i所需硬幣的最小數
- 確定遞推公式
湊足總額為j - coins[i]的最少個數為dp[j - coins[i]]，那么只需要加上一個錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]（考慮coins[i]）。并且dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
所以遞推公式為dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
- dp數組如何初始化
首先湊足總金額為0所需錢幣的個數一定是0，那么dp[0] = 0;
從遞推公式可以看出，非0下標的dp[j]必須初始化為一個最大的數，否則就會在min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。所以下標非0的元素都是應該是最大值INT_MAX。
- 確定遍歷順序
由于本題求錢幣最小個數，那么錢幣的選取有順序和沒有順序都可以。
所以本題外層for循環遍歷物品，內層for遍歷背包或者外層for遍歷背包，內層for循環遍歷物品都是可以的。下面代碼采用硬幣放在外循環，總金額在內循環的方式。
本題是完全背包類似問題，所以遍歷的內循環是正序。
- 舉例推導dp數組
距離：coins = [1, 2, 5], amount = 5，dp狀態圖如下：
代碼：
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX); //從coins中任取硬幣，達到總金額為i所需硬幣的最小數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);return dp[amount] == INT_MAX ? -1 : dp[amount];}
};Leetcode?279.完全平方數
題目鏈接：279 完全平方數
題干：給你一個整數?
n?，返回?和為?n?的完全平方數的最少數量?。完全平方數?是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，
1、4、9?和?16?都是完全平方數，而?3?和?11?不是。
1 <= n <= 104
思考：動態規劃。完全平方數就是物品（可以無限件使用），湊個正整數n就是背包。
- 確定dp數組（dp table）以及下標的含義
dp[j]：達到累計和為i，最少所需完全平方數個數
- 確定遞推公式
dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以湊成dp[j]。并且要選擇最小的dp[j]
所以遞推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
- dp數組如何初始化
dp[0]表示 和為0的完全平方數的最小數量，因此dp[0]一定是0。
從遞歸公式可以看出每次dp[j]都要選最小的，所以非0下標的dp[j]一定要初始為最大值，這樣dp[j]在遞推的時候才不會被初始值覆蓋。
- 確定遍歷順序
由于本題求滿足條件的完全平方數最少個數，那么完全平方數的選取有順序和沒有順序都可以。
所以本題外層for循環遍歷物品，內層for遍歷背包或者外層for遍歷背包，內層for循環遍歷物品都是可以的。下面代碼采用完全平方數放在外循環，累加和在內循環的方式。
本題是完全背包類似問題，所以遍歷的內循環是正序。
- 舉例推導dp數組
舉例：n為5，dp狀態圖如下：
代碼：
class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX); //dp[i]表示達到累計和為i，最少所需完全平方數個數dp[0] = 0;for (int i = 1; i * i <= n; i++) //遍歷完全平方數for (int j = i * i; j <= n; j++) //遍歷累加和if (dp[j - i * i] != INT_MAX) //初始最大值不處理dp[j] = min(dp[j], dp[j - i * i] + 1);return dp[n];}
};自我總結：
- 動態規劃中確定遞歸順序中：
- 如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。
- 如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。
)
