leetcode?70. 爬樓梯

?題目鏈接：70. 爬樓梯 - 力扣（LeetCode）

本題可以用背包問(wèn)題來(lái)解決，就相當(dāng)于樓頂是背包，臺(tái)階是物品，相當(dāng)于之前寫法的進(jìn)階版。

代碼實(shí)現(xiàn)

class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1,0);dp[0] = 1;for(int i = 1;i <= n;i++) {for(int j = 1;j <= 2;j++) {if(i - j >= 0) dp[i] += dp[i - j];}}return dp[n];}
};

leetcode?322. 零錢兌換

題目鏈接：322. 零錢兌換 - 力扣（LeetCode）

視頻鏈接：動(dòng)態(tài)規(guī)劃之完全背包，裝滿背包最少的物品件數(shù)是多少？| LeetCode：322.零錢兌換_嗶哩嗶哩_bilibili

題目概述

給你一個(gè)整數(shù)數(shù)組?coins?，表示不同面額的硬幣；以及一個(gè)整數(shù)?amount?，表示總金額。

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

你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

示例?1：

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

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

思路

1.確定dp數(shù)組含義：dp[j]：湊足總額為j所需錢幣的最少個(gè)數(shù)為dp[j]。

2.確定遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])。

3.數(shù)組初始化：dp[0]=0,非0下標(biāo)初始化成最大值。（以前都是max，這次是min）

4.確定遍歷順序：本題不用強(qiáng)調(diào)順序，本題既不是組合數(shù)也不是排列數(shù)，第一層遍歷物品和背包哪個(gè)都行，第二層也是。

5.打印dp數(shù)組：

?

代碼實(shí)現(xiàn)（先物品后背包）

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 - coins[i]]是初始值則跳過(guò)dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}
};

代碼實(shí)現(xiàn)（先背包后物品）

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

leetcode?279.完全平方數(shù)

題目鏈接：279. 完全平方數(shù) - 力扣（LeetCode）

視頻鏈接：動(dòng)態(tài)規(guī)劃之完全背包，換湯不換藥！| LeetCode：279.完全平方數(shù)_嗶哩嗶哩_bilibili

題目概述

給你一個(gè)整數(shù)?n?，返回?和為?n?的完全平方數(shù)的最少數(shù)量?。

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

示例?1：

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

示例 2：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9

本題和上一道題其實(shí)都差不多，換湯不換藥的的東西。

代碼實(shí)現(xiàn)（先物品后背包）

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

代碼實(shí)現(xiàn)（先背包后物品）

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 - j * j] + 1, dp[i]);}}return dp[n];}
};