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 1if n == 1:return 1if n == 2:return 2return 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 1if n == 1:return 1if 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]intfunc 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]
}