爬楼梯Python3

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

示例 1：
输入：2
输出：2
解释：有两种方法可以爬到楼顶。1 阶 + 1 阶 和 2 阶

解题思路：
实现了两种方法，但是第一种超出时间限制 (｡ì _ í｡)，因为递归的时候方法实际计算了两次。两种方法都使用了动态规划思想，比如对于爬 10 阶楼梯，我们最后一步爬上第 10 阶只会有两种情况，一种是从 9 阶楼梯爬 1 个台阶，一种是从 8 阶台阶爬 2 两个台阶上来。所以 10 阶台阶问题可以划分为爬 9 阶和 8 阶两个子问题，一直递归划分到只剩 2 阶（2 种方法）和 1 阶（一种方法）。

超出时间限制的代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2:
            if n==2:
                return 2
            else:
                return 1
        else:
            return self.climbStairs(n-1)+self.climbStairs(n-2)

第二种方法（没有重复计算）：

class Solution:
    def climbStairs(self, n: int) -> int:
        m = [0,1,2]
        for i in range(3,n+1):
            m.append(m[i-1]+m[i-2])
        return m[n]

时间与空间复杂度如下：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…