Leetcode｜70. 爬楼梯【笔记】-白红宇

Leetcode｜70. 爬楼梯【笔记】

阅读量：712 次

发布时间：2019-03-21

本文共 1026 字，大约阅读时间需要 3 分钟。

爬楼梯问题解析

爬楼梯问题要求我们计算爬到n阶楼梯的不同方法数，每次可以爬1或2阶台阶。这个问题可以通过斐波那契数列来解决，其解答方法包括递归、动态规划、矩阵快速幂等。

4种常见解法：

递归方法

递归的思路是用费波那契的性质: f(n) = f(n-1) + f(n-2)

例子：

import functools@functools.lru_cache(maxsize=None)def climbStairs(n: int) -> int:    if n == 1:        return 1    if n == 2:        return 2    return climbStairs(n - 1) + climbStairs(n - 2)

动态规划优化

使用动态规划存储前两步结果，节省空间。

例子：

def climbStairs(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

斐波那契公式

使用矩阵快速幂或公式直接计算。

例子：

import mathdef climbStairs(n: int) -> int:    if n < 2:        return 1    sqrt5 = math.sqrt(5)    return int(( (1 + sqrt5) ** (n + 1) - (1 - sqrt5) ** (n + 1) ) / (2 * sqrt5))

斐波那契数列的通项

借助斐波那契数列的通项计算。

例子：

import mathdef climbStairs(n: int) -> int:    if n == 1:        return 1    elif n == 2:        return 2    elif n < 0:        return 0    return _fib(n + 1)