70. 爬樓梯 （進階）

題目鏈接：

題目頁面

求解思路：

動規五部曲

1. 確定dp數組及其下標含義：爬到有i階樓梯的樓頂，有dp[i]種方法
2. 遞推公式：dp[i] += dp[i-j];
3. dp數組的初始化：dp[0] = 1;
4. 確定遍歷順序：排列問題，先遍歷物品，再遍歷背包；完全背包，遍歷順序都為正序
5. 舉例推導dp數組：

代碼：

#include <iostream>
#include <vector>
using namespace std;int main(){int n, m;cin >> n >> m;vector<int> dp(n+1, 0);dp[0] = 1;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (i >= j) dp[i] += dp[i-j];}}cout << dp[n] << endl;
}

322. 零錢兌換

題目鏈接：

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺

求解思路：

動規五部曲

1. 確定dp數組及其下標含義：湊足總額為j所需錢幣的最少個數為dp[j]
2. 確定遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3. dp數組的初始化：dp[0] = 0，因為湊足0元所需的錢幣個數是0；其余下標初始化為int的最大值，為了避免遞推公式中初始值覆蓋結果值
4. 確定遍歷順序：這里求錢幣最小個數，和順序沒有關系，不強調組合或是排列，因此先遍歷背包或是物品都可以；因為是完全背包，所以都是正序遍歷
5. 舉例推導dp數組：coins = [1, 2, 5], amount = 5為例，如圖

代碼：

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];}
};

279.完全平方數

題目鏈接：

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺

求解思路：

動規五部曲

1. dp數組及其下標含義：和為j的完全平方數的最少數量為dp[j]
2. 遞推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
3. dp數組的初始化：dp[0] = 0；其余下標初始化為int的最大值
4. 確定遍歷順序：先遍歷物品或背包都可以；因為是完全背包，所以都是正序遍歷
5. 舉例推導dp數組：n=5，如圖

代碼：

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