day45第九章动态规划(二刷）

今日任务

• 70.爬楼梯(进阶)
• 322.零钱兑换
• 279.完全平方数

---

70.爬楼梯(进阶)

题目链接：

https://leetcode.cn/problems/climbing-stairs/description/

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

题解代码：

class Solution {
public://二刷复习动态规划，用完全背包地方式做一次int climbStairs(int n){vector<int> dp(n+1, 0); //定义dp数组，dp[i]表示爬到有i个台阶的楼顶，有dp[i]种方法dp[0] = 1; //初始化dp数组，dp[0]是其他数值的基础，所以要是1for(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];}//一刷动态规划 /*int climbStairs(int n) {//再用完全背包的方式做一次 vector<int> dp(n+1,0);//定义dp数组，dp[i]表示爬到有i个台阶的楼顶，有dp[i]种方法dp[0] = 1; //初始化dp数组，dp[0]是其他数值的基础，所以要是1for(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];/*if(n <= 1){return n; }vector<int> dp(n+1); //定义dp数组，dp[i]代表到第i层有dp[i]种办法dp[1] = 1;  //初始化dp数组，注意这里不初始化dp[0]dp[2] = 2;for(int i = 3; i <= n; i++){//注意i是从3开始的dp[i] = dp[i-1] + dp[i-2];//递推方程}return dp[n];*//* }*///二刷复习动态规划//斐波那契数列式完成/*int climbStairs(int n){if(n <= 1){return n;}vector<int> dp(n+1); //dp数组，dp[i]代表到第i层有dp[i]种方法dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}*/
};

---

322.零钱兑换

题目链接：

https://leetcode.cn/problems/coin-change/description/

题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 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 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

题解代码：

class Solution {
public://二刷动规复习int coinChange(vector<int>& coins, int amount){vector<int> dp(amount+1, INT_MAX); //dp数组，dp[j]表示凑足总数为j所需要的钱币的最少个数为dp[j]dp[0] = 0; //初始化dp数组，dp[0]凑足总数为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];}//一刷动规复习/*int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1, INT_MAX); //dp数组，dp[j]表示凑足总数为j所需的钱币的最少个数为dp[j]dp[0] = 0;//初始化dp数组，dp[0]凑足总数为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.完全平方数

题目链接：

https://leetcode.cn/problems/perfect-squares/description/

题目描述：

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n =12输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n =13输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

题解代码：

class Solution {
public://二刷动规复习int numSquares(int n){vector<int> dp(n+1, INT_MAX); //定义dp数组，dp[j]表示和为j的完全平方数的最小数量dp[j]dp[0] = 0; //和为0的完全平方数的最小数量为dp[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];}//一刷动规/*int numSquares(int n) {vector<int> dp(n+1,INT_MAX);//定义dp数组，dp[j]表示和为j的完全平方数的最小数量d[j]dp[0] = 0; //和为0的完全平方数的最小数量为dp[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];}*/
};

---

总结

我们知道这是完全背包，

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。