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 <= 121 <= coins[i] <= 231 - 10 <= 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循环遍历物品。