70. 爬楼梯 python3 四种解法

布满荆棘的人生 2022-05-07 08:16 139阅读 0赞

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

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

注意：给定 n 是一个正整数。

示例 1：

输入： 2  
输出： 2  
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶  
    示例 2：

输入： 3  
输出： 3  
解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

### python3 ###

class Solution:
    	# 解法 1 递归 + lru 缓存
    	@lru_cache(100)  # 缓存装饰器
    	def stair(n):
    	    if n == 1:
    	        return 1
    	    if n == 2:
    	        return 2
    	
    	    return stair(n - 1) + stair(n - 2)
    
    
    	# 解法2 dp 存储O(n)
        def stair_dp(n: int):
    	    dp = { 1: 1, 2: 2}
    	    for i in range(3, n + 1):
    	        dp[i] = dp[i - 2] + dp[i - 1]
    	    return dp[n]
    
        # 解法3 dp + 只存储 0,1,2 空间复杂度 O(1)
        def climbStairs(self, n):
            nums = [0,1,2]
            if n>=3:
                for i in range(3,n+1):
                    nums.append(nums[i-2] + nums[i-1])
            return nums[n]     
            
    	def climbStairs1(self, n):
            if n ==1 : return  1
            a , b = 1 ,2
            for i in range(2,n):
                a , b = b , a+ b
            return b

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 70：爬楼梯

昨天拿到题一样的思路，递推嘛 class Solution: def climbStairs(self, n: int) -> int: ...

港控/mmm°/ 2024年04月19日 09:56/ 0 赞/ 94 阅读

相关 70. 爬楼梯

70. 爬楼梯题干描述解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如何初始化

爱被打了一巴掌/ 2023年10月16日 15:52/ 0 赞/ 58 阅读

相关 70. 爬楼梯

//到达n阶只可能来自n-1和n-2,所以f(n)=f(n-1)+f(n-2) //1 2 3 5 8 13 int climbStairs(int n

川长思鸟来/ 2023年10月09日 10:32/ 0 赞/ 49 阅读

相关 Leetcode70爬楼梯---两种解法

Leetcode70爬楼梯—两种解法 [题目链接][Link 1] 题目题目描述 > 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > 每次你可以爬

水深无声/ 2022年10月27日 12:07/ 0 赞/ 156 阅读

相关 70. 爬楼梯

> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > > 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ > > 注意：给定 n 是一个正整数。

梦里梦外;/ 2022年10月08日 15:20/ 0 赞/ 186 阅读

相关 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

超、凢脫俗/ 2022年10月07日 07:49/ 0 赞/ 184 阅读

相关 70.爬楼梯

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例：输入： 2 输出

ゝ一纸荒年。/ 2022年09月13日 04:16/ 0 赞/ 199 阅读

相关 70. 爬楼梯 python3 四种解法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

阳光穿透心脏的1/2处/ 2022年05月08日 14:38/ 0 赞/ 144 阅读

相关 70. 爬楼梯 python3 四种解法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

布满荆棘的人生/ 2022年05月07日 08:16/ 0 赞/ 140 阅读

相关 70.爬楼梯

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 // // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ // // 注意：给定

古城微笑少年丶/ 2021年06月22日 15:38/ 0 赞/ 425 阅读