面試題 08.01. 三步問題 - 力扣（LeetCode）

1、狀態表示：

題目要求：上到n階臺階，有多少種方法。那么n逐漸簡化，上1階臺階有多少種方法；上2階臺階有多少種方法……直到上n階臺階有多少種方法。

那么，狀態表示dp[i]：上n階臺階有多少種方法。

2、狀態轉移方程：

上1階臺階：從地面到1，0-》1。1種方法，dp[1] = 1

上2階臺階：從地面到2，0-》2；或者從1到2，0-》1-》2。2兩種方法,dp[2] = 2

上3階臺階：0-》3；或者0-》1-》3；或者0-》1-》2-》3；或者0-》2-》3。4種方法。dp[3] = 4

上4階臺階：1-》4；2-》4，3-》4。那么從1-》4，就先需要上1階臺階，1種方法；從2-》4，就先需要上2階臺階，2種方法；從3-》4，就先需要上3階臺階，4種方法。一共dp[4] = 7,dp[4] = dp[1] + dp[2] + dp[3]。

……

那么，要想走到第i階臺階，就有三種情況：從i-1直接到i，從i-2直接到i，從i-3直接到i。

那么求走到第i階臺階的方法dp[i]，就應該先知道dp[i-1],dp[i-2],dp[i-3]，那么dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

3、初始化：

由狀態轉移方程可知，至少需要初始化前三個狀態。

那么，地面可認為dp[0]，那么dp[0]應該如何初始化呢？其實這里初始化0或1都沒有關系，因為o0或1都可以解釋得通。

我這里就初始化為1了。因為從0-》3，是一種方法，那么dp[3] = dp[0] + dp[1] + dp[2]，方便寫代碼。

4、遍歷順序：

顯然就是從左到右遍歷。

5、返回值：

那么就是dp[n]。

class Solution {
public:int waysToStep(int n) {//越界檢查if(n == 1 || n == 0) return 1;if(n == 2) return 2;const int MOD = 1e9 + 7;vector<int> dp(n+1);//創建dp表dp[0] = dp[1] = 1,dp[2] = 2;//初始化for(int i = 3;i<=n;i++)//遍歷順序dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3])%MOD;//狀態轉移return dp[n];}
};

同樣這里也可以用滾動數組優化。