在这里插入图片描述

  • 这道题很像斐波那契数列,但是初始值不同,也有动态规划的解法,但是一开始我想到的是递归写法。
  • 现在我们站在第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]
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部