題目
三步問(wèn)題。有個(gè)小孩正在上樓梯，樓梯有n階臺(tái)階，小孩一次可以上1階、2階或3階。實(shí)現(xiàn)一種方法，計(jì)算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對(duì)結(jié)果模1000000007。
示例1:
輸入：n = 3?
輸出：4
說(shuō)明: 有四種走法
示例2:
輸入：n = 5
輸出：13
提示:n范圍在[1, 1000000]之間
思路
- 到0階臺(tái)階的方式：（地平線）
- 到1階臺(tái)階的方式：1種（0->1）
- 到2階臺(tái)階的方式：2種（0->2、到1階臺(tái)階的方式1種（0->1->2））
- 到3階臺(tái)階的方式：4種（0->3、到1階臺(tái)階的方式1種、到2階臺(tái)階的方式2種）
- 到4階臺(tái)階的方式：7種（到1階臺(tái)階的方式1種、到2階臺(tái)階的方式2種、到3階臺(tái)階的方式4種）
- 到5階臺(tái)階的方式：13種
- ......
step1：狀態(tài)表示
經(jīng)驗(yàn)（以某一個(gè)位置為起點(diǎn)或結(jié)尾）+題目要求（做替換即可）：
dp[i]表示：到達(dá)i位置時(shí)，一共有多少種方式。
step2：狀態(tài)轉(zhuǎn)移方程
以i位置的最近一次位置來(lái)劃分問(wèn)題——dp[i]有3種情況：
- 從i - 3位置跳3步一次性到達(dá)i位置。到i - 3位置有dp[i - 3]種方式，后面再加一步到i位置，則到i位置有dp[i - 3]種方式。
- 從i - 2位置跳2步一次性到達(dá)i位置。同理：則到i位置有dp[i - 2]種方式。
- 從i - 1位置跳1步一次性到達(dá)i位置。同理：則到i位置有dp[i - 1]種方式。
得狀態(tài)轉(zhuǎn)移方程為：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
step3：初始化
令dp[1] = 1、dp[2] = 2、dp[3] = 4，這樣就不會(huì)越界。
step4：填表順序
從左往右。
step5：返回值
返回dp[n]。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-454963.html
代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-454963.html
class Solution {
public int waysToStep(int n) {
int MOD = (int)1e9 + 7;
//處理邊界條件
if(n == 1 || n == 2) {
return n;
}
if(n == 3) {
return 4;
}
//1.創(chuàng)建 dp 表
int[] dp = new int[n + 1]; //要訪問(wèn)到 n 的位置，所以 dp 表規(guī)模要是 n + 1 大小
//2.初始化
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
//3.填表
for(int i = 4; i <= n; i++) {
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
//4.返回值
return dp[n];
}
}到了這里，關(guān)于3-【斐波那契數(shù)列模型】LeetCode面試題08.01-三步問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
