云奇网站建设,猪八戒建站服务,微信小程序商店,建设科普网站的意义今日任务
70.爬楼梯(进阶)322.零钱兑换279.完全平方数 70.爬楼梯(进阶)
题目链接#xff1a;
https://leetcode.cn/problems/climbing-stairs/description/
题目描述#xff1a;
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不…今日任务
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){vectorint dp(n1, 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) {//再用完全背包的方式做一次 vectorint dp(n1,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-j0){dp[i] dp[i-j];}}}return dp[n];/*if(n 1){return n; }vectorint dp(n1); //定义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;}vectorint dp(n1); //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(vectorint coins, int amount){vectorint dp(amount1, 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(vectorint coins, int amount) {vectorint dp(amount1, 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){vectorint dp(n1, 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) {vectorint dp(n1,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循环遍历物品。
