假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例

示例1

输入:n = 2

输出:2

解释:有两种方法可以爬到楼顶。

1)1 阶 + 1 阶

2)2 阶

示例2

输入:n = 3

输出:3

解释:有三种方法可以爬到楼顶。

1)1 阶 + 1 阶 + 1 阶

2)1 阶 + 2 阶

3)2 阶 + 1 阶

解析

1)爬楼梯问题,是一个典型的斐波拉契数列,上第n级台阶,可以从n-1跨一步,或者n-2一次跨两步,直接加和;

2)斐波拉契最直观的解法,是用递归,但递归方法计算量大,改进为动态规划问题,即将前面计算过的存起来,避免重复计算。

代码示例

def climbStairs(self, n: int) -> int:
    lst = [1, 2]
    if n < 3:
        return lst[n-1]
    for i in range(3, n+1):
        lst.append(lst[i-2] + lst[i-3])
    return lst[-1]

print(climbStairs(3))

执行用时:28 ms, 在所有 Python3 提交中击败了 96.87% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/365