leetcode 70: 爬楼梯

leetcode 70: 爬楼梯

题目描述：
假设你正在爬楼梯。需要 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 阶
思路1：
利用递归和记忆化的结合：
f(n) = f(n-1)+f(n-2)
f(0) = 1
f(1) = 1
类似于斐波那契数列，但是这种方法的时间复杂度较高，因为进行类递归。
思路2：
动态规划：采用递归和记忆化的方式可以解决的问题，一般都可以通过dp的方式解决。
dp解决问题的两个关键点：
（1）dp状态的定义，非常重要，决定了问题是否好解，以及（2）是否易得
（2）dp的状态转移方程
本题的代码为：

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

时间复杂度为：O(n) 空间复杂度也为O(n)，因为使用了一个数组。
为了简化空间复杂度为O(1)可以改为：

class Solution:
    def climbStairs(self, n: int) -> int:
        a = 1
        b = 1
        for i in range(2, n+1):
            a, b = a+b, a 
        return a