面試題 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];}
};
同樣這里也可以用滾動數組優化。