【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?1$階或$i?2$階樓梯而來，因此只需要將相鄰兩階的方案數加起來，就能得到下一階的方案數。

初始值$0$階樓梯的方案數為$1$，$1$階樓梯的方案數為$1$。

• 時間復雜度$O(n)$
• 空間復雜度$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