首页 > 编程语言 >leetcode算法热题-爬楼梯

leetcode算法热题-爬楼梯

时间:2024-05-01 10:33:36浏览次数:29  
标签:楼顶 爬楼梯 示例 int 复杂度 热题 方法 leetcode

题目

假设你正在爬楼梯。需要 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.

提示:

1 <= n <= 45

解答

这是一个斐波那契数列的变形,我们在第一层时为1,第二层为2,第三层则为第一层和第二层相加,从第三层开始后面的每一层都是前两层相加,即F(n)=F(n-1)+F(n-2),n>=3。我们定义一个数组F[n]来存储爬n阶楼梯有多少种方法,使用for循环从第三阶楼梯开始循环,求得F[n]。

代码
class Solution {
public:
    int climbStairs(int n) { 
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int F[n+1];
        F[1] = 1;
        F[2] = 2;
        for(int i = 3;i <= n;i++)
        {
            F[i] = F[i-1] + F[i-2];
        }
        return F[n];
    }
};
复杂度分析

时间复杂度:O[n],使用了一个for循环来求解。
空间复杂度:O[n],定义了一个数组F[n+1]来存储爬各阶楼梯的方法总数。

标签:楼顶,爬楼梯,示例,int,复杂度,热题,方法,leetcode
From: https://www.cnblogs.com/oyoy/p/18168834

相关文章

  • 347. 前 K 个高频元素(leetcode)
    https://leetcode.cn/problems/top-k-frequent-elements/description/可以考虑使用HashMap+排序,不过直接使用优先队列也挺不错,可以使用大顶堆或小顶堆classSolution{publicint[]topKFrequent(int[]nums,intk){Map<Integer,Integer>map=newHas......
  • 239. 滑动窗口最大值(leetcode)
    https://leetcode.cn/problems/sliding-window-maximum/简单的滑动窗口,但是与ACM模式的维护数组不同,在leetcode定义单调队列类更加方便classMyQueue{//单调队列实现,递减Deque<Integer>deque=newLinkedList<>();voidpoll(intval){if(!deque......
  • leetcode算法热题--字母异位词组合
    题目给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],[&q......
  • leetcode算法热题--两树之和
    题目给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值`target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1:输入:nums=[2,7,11,15......
  • 【LeetCode 1648】销售价值减少的颜色球
    题目描述原题链接:LeetCode.1648销售价值减少的颜色球解题思路题意很容易理解,就是每次挑剩余同色球数量最大的颜色卖得到最大价值,总共卖orders个球的最大总价值;最快速直观暴力的解法是按照同色球数量排序,每次取数量最大值累加到总价值中并且将数量减一后重新排序,重复or......
  • leetcode(力扣) 2866. 美丽塔 II
    原题链接暴力做法(时间复杂度O(n^2))每次选取下标i为峰值,进行n次,对每次取max就可以找打答案对于i左边的序列:需要满足序列是非递减的,同时每个值尽可能大所以满足:下标为j的位置上的数<=下标是(j,i]的最小的值(等于时取得最大值),同时需要保证j位......
  • 38天【代码随想录算法训练营34期】第九章 动态规划part01 (● 理论基础 ● 509. 斐波
    理论基础斐波那契数classSolution:deffib(self,n:int)->int:ifn==0:return0ifn==1:return1returnself.fib(n-1)+self.fib(n-2)爬楼梯classSolution:defclimbStairs(self,n:int)->i......
  • LeetCode三则
    72.编辑距离给你两个单词word1和word2,请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作:插入一个字符删除一个字符替换一个字符示例1:输入:word1="horse",word2="ros"输出:3解释:horse->rorse(将'h'替换为'r')rorse->rose(删......
  • 56. 合并区间(leetcode)
    https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked合并区间练习题typedefpair<int,int>PII;vector<PII>segs;classSolution{public:vector<vector<int>>merge(vector<vector<int>>......
  • LeetCode三则
    5.最长回文子串给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s仅由数字和英文字母组成cl......