70. 爬楼梯

题目

• 题号：70
• 难度：简单
• https://leetcode-cn.com/problems/climbing-stairs/

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

实现

思路1 动态规划

首先我们定义f(x)表示爬到第x级台阶的方案数。由题目得，要跳到第x级台阶，只有可能从第x-1级台阶或第x-2级台阶调过来的。所以我们可以列出动态转移方程：

值得注意的是这里f(x)只跟f(x-1)和f(x-2)有关，所以我们只开辟三个变量的空间分别存储上式的三个元素。

class Solution:
    def climbStairs(self, n: int) -> int:
        x1, x2, res = 0, 0, 1
        for i in range(n):
            x1 = x2
            x2 = res
            res = x1+x2
        return res