day-45 代码随想录算法训练营（19）动态规划 part 07

70.爬楼梯（进阶）

分析：基本动态规划转换为完全背包，因为1、2 两种上楼梯方式是无限选择的

思路：

• 1. j 表示 容量为 j 时，装满有dp[j]种方法
• 2. dp[j]+=dp[j-nums[i]]
• 3. 初始化 dp[0]=1,dp[1]=1
• 4. 遍历顺序：外层遍历容量  内层遍历物品

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

 

322.零钱兑换

分析：硬币无限，组合成金额 -> 完全背包（组合）

思路：

1. 1.dp存储：金额为 j 时，有 dp[j] 种方法
2. 2.dp[j]=min(dp[j],dp[j-coins[i]]+1)
3. 3.dp[0]=0
4. 4.遍历顺序：外层遍历硬币，内层遍历容量

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.完全平方数

思路：

• 1.dp存储： 容量为 j 时，装满的最少使用数字为dp[j]种方法

• 2.dp[j]=min(dp[j],dp[j-i*i]+1)

• 3.初始化：dp[0]=0  INT_MAX

• 4.遍历顺序：外层遍历数字，内层遍历容量

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