No.70 爬楼梯

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

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

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

题解：
斐波那契数列
根据题意可知，在爬上任意的第级台阶时，存在两种可能性：从 爬两级到，或者从爬一级到。那么，如果假设有种方法到达、有种方法到达、有种方法到达，则显然到达的方法数量。
再看初始情况，如果只有一级台阶，则只有一种方法即爬一级，。
如果只有两级台阶，则有两种方法，即一次爬两级和两次爬一级，。
至此我们可以得出结论，这道题的数学模型本质上就是求解斐波那契数列。

一、暴力递归

class Solution:
    @functools.lru_cache(100)  # 缓存装饰器
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

作者：821218213
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/70zhong-quan-chu-ji-python3hui-ji-liao-ti-jie-qu-w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

知识点：
复杂度分析——递归树

如图所示，由于每一层递归都要重复地计算下层的值，因此计算量和递归树节点数量一致，时间复杂度为。
每一层递归只需要记录中间值，其数量和递归树深度一致，空间复杂度为。

二、记忆化递归

def climbStairsMemo(n:int,memo:List) -> int:
    if n==0 or n==1:
        memo[n]=1
    else:
        memo[n]=climbStairsMemo(n-1,memo)+climbStairsMemo(n-2,memo)
    return memo[n]

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

三、动态规划

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {}
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

作者：821218213
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/70zhong-quan-chu-ji-python3hui-ji-liao-ti-jie-qu-w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

没什么好说的，就是沿着数组逐个算过去。

四、动态规划优化——滚动数组**

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

作者：821218213
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/70zhong-quan-chu-ji-python3hui-ji-liao-ti-jie-qu-w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

由于三中动态规划需要保存整个斐波那契数列，空间复杂度为。但根据递推公式可以看出，n-2之前的计算结果是完全不需要保存的，因此我们维护一个长度为2的滚动数组来保存所需要的值、即可将空间复杂度降低至。

五、矩阵快速幂**

def mat_mul_2x2(A,B):
    return [
            [A[0][0]*B[0][0]+A[0][1]*B[1][0],
             A[0][0]*B[0][1]+A[0][1]*B[1][1]],
            [A[1][0]*B[0][0]+A[1][1]*B[1][0],
             A[1][0]*B[0][1]+A[1][1]*B[1][1]]
           ]

def mat_mul_2x1(A,b):
    return [A[0][0]*b[0]+A[0][1]*b[1],
            A[1][0]*b[0]+A[1][1]*b[1]]

def mat_pow(mat,n):
    #矩阵快速幂
    if n==1:
        return mat
    if n%2==0:
        tmp=mat_pow(mat,n//2)
        return mat_mul_2x2(tmp,tmp)
    elif n%2!=0:
        return mat_mul_2x2(mat_pow(mat,n-1),mat)

class Solution:
    def climbStairs(self, n: int) -> int:
        M=[[1,1],[1,0]]
        res=mat_mul_2x1(mat_pow(M,n),[1,1])
        return res[1]

递归快速幂会产生大量内存开销，因此最好将递归转化为循环形式。

def mat_pow(mat,n):
    #矩阵快速幂
    res=[[1,0],[0,1]]
    if n==1:
        return mat
    while n:
        if n%2!=0:
            res=mat_mul_2x2(res,mat)
        n=n//2
        mat=mat_mul_2x2(mat,mat)
    return res

知识点：
快速幂与矩阵快速幂
朴素幂运算

时间复杂度，空间复杂度
快速幂
若为偶数：
若为奇数：
时间复杂度，递归空间复杂度，循环空间复杂度

六、暴力套公式**

class Solution:
    def climbStairs(self, n: int) -> int:
        import math
        sqrt5=5**0.5
        fibin=math.pow((1+sqrt5)/2,n+1)-math.pow((1-sqrt5)/2,n+1)
        return int(fibin/sqrt5)

作者：821218213
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/70zhong-quan-chu-ji-python3hui-ji-liao-ti-jie-qu-w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

会被面试官打死，但是很快。