假設(shè)你正在爬樓梯绣的。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階欲账。你有多少種不同的方法可以爬到樓頂呢被辑？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂敬惦。
- 1 階 + 1 階
- 2 階
示例 2：輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂盼理。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/climbing-stairs
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)俄删，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處宏怔。
動(dòng)態(tài)規(guī)劃
推導(dǎo)過程：
1階：1
2階：1+1、2
3階：1+1+1畴椰、1+2臊诊、2+1
...
n階：(n-1)階次數(shù) + (n-2)階次數(shù)
就比如：站在第n階臺(tái)階上，第一次可以下1個(gè)臺(tái)階斜脂，也可以下2個(gè)臺(tái)階抓艳，然后問題就轉(zhuǎn)化成 “在(n-1)個(gè)臺(tái)階上走下去有幾種可能” 和 “在(n-2)個(gè)臺(tái)階上走下去有幾種可能” 之和
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int first = 1, second = 2, third = -1;
for (int i = 2; i < n; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
}
運(yùn)行效率
