LeetCode｜70.爬楼梯

• 这道题很像斐波那契数列，但是初始值不同，也有动态规划的解法，但是一开始我想到的是递归写法。
• 现在我们站在第n阶台阶，那么，我们上一步就有两种可能：1、我们从第n-1阶台阶走一步上来的；2、我们从第n-2阶台阶直接走两步上来的。
• 那么我们走到第n阶台阶的方法数量就等于我们走到第n-1阶台阶的方法数量加上第n-2阶台阶的方法数量之和。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 1
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

• 这就是我最初写出来的代码，其实很接近了，但是这样直接超时了，因为会有很多重复计算！
• 这种情况可以把计算好的结果给存下来，这样就不用重复计算了，也是空间换时间的一种方式。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 定义一个字典用于存储已经计算过的结果
        memo = {}

        # 定义递归函数
        def helper(n):
            # 如果 n 已经在 memo 中，直接返回
            if n in memo:
                return memo[n]
            
            # 基本情况
            if n == 0:
                return 1
            if n == 1:
                return 1
            if n == 2:
                return 2
            
            # 递归调用并存储结果
            nums1 = helper(n - 1)
            nums2 = helper(n - 2)
            memo[n] = nums1 + nums2  # 存储结果
            
            return memo[n]
        
        return helper(n)

• 官方题解 - 动态规划+滚动数组

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

• 官方题解 - 矩阵快速幂【很高效，遇到过好几次了】

type matrix [2][2]int

func mul(a, b matrix) (c matrix) {
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
        }
    }
    return c
}

func pow(a matrix, n int) matrix {
    res := matrix{{1, 0}, {0, 1}}
    for ; n > 0; n >>= 1 {
        if n&1 == 1 {
            res = mul(res, a)
        }
        a = mul(a, a)
    }
    return res
}

func climbStairs(n int) int {
    res := pow(matrix{{1, 1}, {1, 0}}, n)
    return res[0][0]
}