首页 > 其他分享 >leetcode-70-爬楼梯

leetcode-70-爬楼梯

时间:2022-11-11 10:12:13浏览次数:44  
标签:楼顶 return int range 70 爬楼梯 leetcode dp

转自leetcode,原题链接:https://leetcode.cn/problems/climbing-stairs/

假设你正在爬楼梯。

需要 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

解法一:动态规划,使用dp数据,记录爬i个台阶的可能爬法;

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp = [0] * (n + 1)

        for i in range(3):
            dp[i] = i
        
        for i in range(3,n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

解法二:动态规划,使用3个变量来记录i、i-1、i-2可能的爬法,空间复杂度再一次降低,为O(3)

class Solution:
    def climbStairs(self, n: int) -> int:
        p,q,r = 0,0,1

        for i in range(n):
            p = q
            q = r
            r = p + q
            
        return r

 

标签:楼顶,return,int,range,70,爬楼梯,leetcode,dp
From: https://www.cnblogs.com/hannahlee/p/16879675.html

相关文章

  • 1704. 判断字符串的两半是否相似
    1704.判断字符串的两半是否相似给你一个偶数长度的字符串s。将其拆分成长度相同的两半,前一半为a,后一半为b。两个字符串相似的前提是它们都含有相同数目的元音('a......
  • dell R730 服务器 IBM V7000 centos 7 multipath 存储多路径安装
    我的环境为:DELLR730服务器双口HBA卡联想IBMStorwizeV7000存储交换机:博科6505此文只涉及centos服务器设置​实施:​1.yum-yinstalldevice-mapperdevice-mapp......
  • CF1706D&E
    DEasyVersion枚举最小值\(v\)(\(0\leqv\leqa_1\)),然后我们希望最小化最大值。也就是说,对\(\foralli\),我们在满足\(\lfloor\frac{a_i}{p_i}\rfloor\geqv\)的前提下......
  • LeetCode刷题记录.Day11
    赎金信题目链接代码随想录(programmercarl.com)classSolution{public:boolcanConstruct(stringransomNote,stringmagazine){intrecord[26]={......
  • 70. 爬楼梯
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?思路:这就是动态规划?代码:classSolution{publ......
  • CodeForces - 708C Centroids
    题意:给出一棵有n个结点的树,对于每一个结点,如果任意删除一条边后再任意添加一条边能使这个结点成为这棵树的重心,则输出1;反之输出0。解:重心的特点:以重心为根节点时,其最大子......
  • P2470 [SCOI2007]压缩
    传送门区间DP好题,看到这题很容易想到设\(f[i][j]\)为区间\(i\)~\(j\)内的最短折叠,那么转移方程就为:\[f[i][j]=min_{k=i}^{j-1}(f[i][j],f[i][k]+f[k+1][j])\]然鹅这......
  • 算法 Notes|LeetCode 26. 删除排序数组中的重复项 - easy
    历史LeetCode刷题文章:​​算法Notes|LeetCode349.两个数组的交集-easy​​​​算法Notes|LeetCode14.最长公共前缀-easy​​​​算法Notes|LeetCode1.两数之和......
  • NC207040 丢手绢
    题目描述链接:https://ac.nowcoder.com/acm/problem/207040来源:牛客网牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏,但是小朋友们太小了,不能围成一个均匀的圆圈......
  • LeetCode 763. 划分字母区间
    1、一上来先遍历数组,找到每个字母最后出现的位置。2、再次遍历数组,保持一个last,表示当前至少应该在哪里分割classSolution{public:vector<int>partitionLabel......