🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域新星創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 70. 爬樓梯

? 題目描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階
   示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

1 <= n <= 45

🌟 求解思路&實現代碼&運行結果

---

? 遞歸 -> 記憶化搜索 -> DP

🥦 求解思路

1. 每個位置，我們可以向上爬一個樓梯，也可以爬倆個樓梯，存在著重復子問題的過程，可以通過遞歸來求解，但是遞歸會時間超限。所以，在此基礎上我們可以通過緩存來做，直接通過，最后dp也就呼之欲出啦。
2. 實現代碼如下所示：

🥦 實現代碼 - 遞歸

class Solution {public int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;return climbStairs(n-1)+climbStairs(n-2);}
}

🥦 運行結果

🥦 實現代碼 - 記憶化搜索

class Solution {private int[] map=new int[50];public int climbStairs(int n) {if(map[n]!=0) return map[n];if(n==1) return map[n]=1;if(n==2) return map[n]=2;return map[n]=climbStairs(n-1)+climbStairs(n-2);}
}

🥦 運行結果

🥦 實現代碼 - DP

class Solution {private int[] map=new int[50];public int climbStairs(int n) {map[1]=1;map[2]=2;for(int i=3;i<=n;i++){map[i]=map[i-1]+map[i-2];}return map[n];}
}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！