假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個臺階近速。你有多少種不同的方法可以爬到樓頂呢诈嘿？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂削葱。
1 階 + 1 階
2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂奖亚。
1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階
解題思路
1、第一步 p第一項=0 接下來循環(huán) i=1 p=q q=r r=前倆項之和 依次往下 得到最終的r
代碼
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
解題思路
1析砸、總結(jié)可以得出當(dāng)前值=上一個階梯結(jié)果+上上一個階梯結(jié)果昔字，而上一個又等于上上一個加上上上一個，這中間有重復(fù)得首繁，所以用一個hashmap存起來后查看作郭，就不用每次重復(fù)得遞歸調(diào)用
時間復(fù)雜度高得解法
123.png
