0070. 爬楼梯.md

0070. 爬楼梯

• 标签：动态规划
• 难度：简单

题目大意

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路

先来看一下规律：

第 1 阶台阶：1 种方法（从 0 阶爬 1 阶）

第 2 阶台阶：2 种方法（从 0 阶爬 2 阶，从 1 阶爬 1 阶）

第 i 阶台阶：从第 i-1 阶台阶爬 1 阶，或者从第 i-2 阶台阶爬 2 阶。

则推出递推公式为：F(i) = F(i-1) + F(i-2)

代码

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1 or n == 2:
            return n
        f1 = 1
        f2 = 2
        for i in range(2,n):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3