【LetMeFly】70.爬楼梯：动态规划（递推）
力扣题目链接：https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 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 <= 45
方法一：动态规划（递推）
第 i i i阶楼梯可以由第 i − 1 i-1 i−1阶或 i − 2 i-2 i−2阶楼梯而来，因此只需要将相邻两阶的方案数加起来，就能得到下一阶的方案数。
初始值 0 0 0阶楼梯的方案数为 1 1 1， 1 1 1阶楼梯的方案数为 1 1 1。
- 时间复杂度 O ( n ) O(n) O(n)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:int climbStairs(int n) {int _0 = 1, _1 = 1;for (int i = 2; i <= n; i++) {int _2 = _0 + _1;_0 = _1, _1 = _2;}return _1;}
};
Python
class Solution:def climbStairs(self, n: int) -> int:_0, _1 = 1, 1for i in range(n - 1):_0, _1 = _1, _0 + _1return _1
同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134913892
