70. 爬樓梯
描述
- 假設(shè)你正在爬樓梯。需要 n 步你才能到達(dá)樓頂奴璃。
- 每次你可以爬 1 或 2 個(gè)臺(tái)階瞒滴。你有多少種不同的方法可以爬到樓頂呢？
- 注意：給定 n 是一個(gè)正整數(shù)哮缺。
示例
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂弄跌。
1. 1 步 + 1 步
2. 2 步
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步
思路
- 自底向上的動(dòng)態(tài)規(guī)劃尝苇，狀態(tài)方程為f(n) = f(n-1) + f(n-2)铛只，本質(zhì)是一個(gè)斐波那契數(shù)列問題。
class Solution_70 {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int m1 = 2, m2 = 1, m = 0;
for (int i = 2; i < n; ++i) {
m = m1 + m2;
m2 = m1;
m1 = m;
}
return m;
}
};
