原題地址：https://leetcode-cn.com/problems/climbing-stairs/
題目描述
假設你正在爬樓梯。需要 n 階你才能到達樓頂鸽疾。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢测蘑？
注意：給定 n 是一個正整數(shù)灌危。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂碳胳。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
解題方案：
我們先反著考慮勇蝙，有幾種方案到第i階樓梯，答案是2種：
- 第i-1階樓梯走1步
- 第i-2階樓梯走2步
所以用stepCount[i]來表示到第i階樓梯方案的個數(shù)挨约，就是
stepCount[i] = stepCount[i-1] + stepCount[i-2]
其實把整個數(shù)列列出來就是1味混，2，3诫惭，5翁锡，8....，是一個斐波那契數(shù)列夕土，可以用遞歸馆衔。但如果n過大，遞歸的效率就會很低怨绣，且會占用大量的內(nèi)存角溃；所以換個思路，用動態(tài)規(guī)劃會比較好篮撑。
代碼：
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int[] m = new int[n+1];
m[1] = 1;
m[2] = 2;
for(int i = 3; i<=n; i++) {
m[i] = m[i-1] + m[i-2];?
}
return m[n];
}
}
提交結(jié)果：
image.png
