記字節(jié)前端面試一道簡單的算法題
70. 爬樓梯 （medium）
假設(shè)你正在爬樓梯点弯。需要 n 階你才能到達(dá)樓頂索烹。
每次你可以爬 1 或 2 個(gè)臺(tái)階魄咕。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)销睁。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
- 1 階 + 1 階
- 2 階
方法1.動(dòng)態(tài)規(guī)劃
ds_71
- 思路：因?yàn)槊看慰梢耘?1 或 2 個(gè)臺(tái)階来吩，所以到第n階臺(tái)階可以從第n-2或n-1上來俐银，其實(shí)就是斐波那契的dp方程
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(n)，空間復(fù)雜度O(1)
Js:
var climbStairs = function (n) {
const memo = [];
memo[1] = 1;
memo[2] = 2;
for (let i = 3; i <= n; i++) {
memo[i] = memo[i - 2] + memo[i - 1];//所以到第n階臺(tái)階可以從第n-2或n-1上來
}
return memo[n];
};
//狀態(tài)壓縮
var climbStairs = (n) => {
let prev = 1;
let cur = 1;
for (let i = 2; i < n + 1; i++) {
[prev, cur] = [cur, prev + cur]
// const temp = cur; // 暫存上一次的cur
// cur = prev + cur; // 當(dāng)前的cur = 上上次cur + 上一次cur
// prev = temp; // prev 更新為 上一次的cur
}
return cur;
}
Java:
class Solution {
public int climbStairs(int n) {
int prev = 1, cur = 1;
for (int i = 2; i < n + 1; i++) {
int temp = cur;
cur = prev + cur;
prev = temp;
}
return cur;
}
}
