題目：
LeetCode題目鏈接
題目截圖：
解題步驟：
符合動態規劃的思想
1.定義子問題：爬到第n階可以在第n-1階爬一個臺階，或者在第n-2階
爬兩個臺階，由于是或，所以是+，F(n)表示爬到第n階，所有的方法數
F(n) = F(n - 1) + F(n - 2)
2.反復執行：從2回圈到n，執行上述公式，因為n為1的話，只有一種方式
代碼：
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
// 方式一
// if (n < 2) return 1; // 因為n是正整數，也就是n等于1
// const dp = [1, 1];
// // 陣列的索引表示階數，值表示方法數，之所以將第一個數設為1
// // 是為了方便后面階數的計算，真實情況下，n是不會為0的
// for (let i = 2; i <= n; i++) {
// dp[i] = dp[i - 1] + dp[i - 2];
// }
// // console.log(dp);
// return dp[n];
// 方式二，只維持兩個變數，不停地覆寫上一次的值，因為目的是為了得到最后一個元素的值，
// 不需要全部進行存盤，空間復雜度會變為O(1)，時間復雜度不變，還是O(n)
if (n < 2) return 1;
let dp0 = 1; // 代表dp這個陣列下標為0時的值
let dp1 = 1; // 代表dp這個陣列下標為1時的值
for (let i = 2; i <= n; i++) {
const temp = dp0;
dp0 = dp1;
dp1 = temp + dp0;
// 相當于是只用到了兩個元素，因為只需要得到最后一個元素的值，
// 所以不需要把所有的元素都存盤
}
return dp1;
};
時間復雜度分析：
時間復雜度是O(n)
空間復雜度分析：
空間復雜度是O(n)
怎么樣，是不是很簡單，你學會了嗎 ？
如果這篇文章能夠幫助到您，希望您不要吝惜點贊👍👍和收藏💖💖，您的支持是我繼續努力的動力 💪💪 ！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/251787.html
標籤：其他
上一篇：uni-app開發經驗分享二十一： 圖片滑動解鎖插件制作決議
下一篇：計算公式 - 四則運算實作