一、題目解析

?

此題可以類比第N個泰波那契數

二、算法解析

?1、狀態表示

根據上面的分析和題目要求，dp[i]表示：到達i位置，一共有多少種方法

2、狀態轉移方程

以i位置的狀態，以最近一步劃分問題

dp[i]? ?從i-1->i? dp[i-1]

? ? ? ? ? 從i-2->i? dp[i-2]

? ? ? ? ? 從i-3->i? dp[i-3]

?

3、初始化

計算四節臺階的方法需要前三階各自的方法數，所以初始化dp[1] = 1,dp[2] = 2,dp[3] = 4

4、填dp表的順序

以4為起點，從左往右依次填寫

5、返回值

根據題目要求需要返回在i點的方法數，所以返回dp[n]

小細節：

題目上說數字會過大所以需要模上一個10000000007，也就是1e9+7

老規矩，先去自己實現結合解析，鏈接：面試題 08.01. 三步問題 - 力扣（LeetCode）

三、代碼示例

class Solution {
public:int waysToStep(int n) {const int MOD = 1e9 + 7;//定義模數if(n == 1 || n == 2) return n;//處理邊界條件if(n == 3) return 4;vector<int> dp(n+1);dp[1] = 1,dp[2] = 2,dp[3] = 4;//初始化for(int i = 4;i<=n;i++){dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;//對兩個加法分別取模}return dp[n];//返回結果}
};

?

?四、空間優化

該題空間優化與第N個泰波那契數類似，如果感興趣的朋友可以去看看我之前的博客

鏈接：動態規劃-1137.第N個泰波那契數-力扣(LeetCode)-CSDN博客

看到最后，如果對您有所幫助還請留下免費的贊和收藏，我們下期再見！