題目描述：

三步問題。有個小孩正在上樓梯，樓梯有n階臺階，小孩一次可以上1階、2階或3階。 實現一種方法，計算小孩有多少種上樓梯的方式。 結果可能很大，你需要對結果模1000000007。示例1:輸入：n = 3 輸出：4說明: 有四種走法示例2:輸入：n = 5輸出：13提示: n范圍在[1, 1000000]之間

解決思路：

動態規劃

參考文章：動態規劃之青蛙跳臺階
動態規劃基本思想

動態規劃的實質是分治思想和解決冗余。因此，動態規劃是一種將問題實例分解為更小的/相似的子問題，并存儲子問題的解，使得每個子問題只求解一次，最終獲得原問題的答案，以解決最優化問題的算法策略。

與貪心法的關系：
1.與貪心法類似，都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優解。
2.貪心法選擇當前最優解，而動態規劃通過求解局部子問題的最優解來達到全局最優解。

與遞歸法的關系：
1.與遞歸法類似，都是將問題實例歸納為更小的、相似的子問題。
2.遞歸法需要對子問題進行重復計算，需要耗費更多的時間與空間，而動態規劃對每個子問題只求解一次。對遞歸法進行優化，可以使用記憶化搜索的方式。它與遞歸法一樣，都是自頂向下的解決問題，動態規劃是自底向上的解決問題。

遞歸問題——>重疊子問題——> 1.記憶化搜索（自頂向下的解決問題）；2.動態規劃（自底向上的解決問題）

Java代碼：

遞歸，自頂向下，但是該方法會超時

class Solution {public int waysToStep(int n) {int mod = 1000000007;if(n<=2) return n;if(n==3) return 4;//遞歸return ((waysToStep(n-1)+waysToStep(n-2))%mod+waysToStep(n-3))%mod;} }

回溯，自底向上

class Solution {public int waysToStep(int n) {int mod = 1000000007;//定義初始數組int[] d = new int[]{1,2,4};//定義中間變量int temp1 = 0;int temp2 = 0;//回溯（動態規劃）if(n<=2) return n;if(n==3) return 4;if(n>3) {for (int i = 4; i <= n ; i++) {//i++之后，現在的d[1]變成d[0],現在的d[2]變成d[1],新產生的d[2]是d[2]temp1 = d[1];temp2 = d[2];//d[2]=d[0]+d[1]+d[2];//不要忘記取余，否則數據會溢出d[2]=( (d[0]+d[1])%mod+d[2] )%mod;//更新d[0]和d[1]d[0] = temp1;d[1] = temp2;}}return d[2];} }

總結

以上是生活随笔為你收集整理的LeetCode——面试题 08.01. 三步问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。