70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
分析：
这是一道经典的动态规划题。很早之前就写过。但是现在学会了使用滚动数组来优化空间复杂度。官方题解还给出了一个利用矩阵快速幂，达到(O(lgn))复杂度的方法。这个方法的原理可以看官方题解，这里给出Python代码实现。
代码（Python）：
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 滚动数组优化
class Solution2:
def climbStairs(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
pre = 1
last = 2
for _ in range(3, n + 1):
temp = pre
pre = last
last = temp + pre
return last
# 矩阵快速幂
class Solution3:
def climbStairs(self, n: int) -> int:
q = [[1, 1], [1, 0]]
res = self.pow(q, n)
return res[0][0]
def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
ret = [[1, 0], [0, 1]]
while n > 0:
if n & 1 == 1:
ret = self.multiply(ret, a)
n >>= 1
a = self.multiply(a, a)
return ret
def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
return c