本專欄內(nèi)容為：算法學(xué)習(xí)專欄，分為優(yōu)選算法專欄，貪心算法專欄，動(dòng)態(tài)規(guī)劃專欄以及遞歸，搜索與回溯算法專欄四部分。 通過(guò)本專欄的深入學(xué)習(xí)，你可以了解并掌握算法。
??博主csdn個(gè)人主頁(yè)：小小unicorn
?專欄分類：動(dòng)態(tài)規(guī)劃專欄
??代碼倉(cāng)庫(kù)：小小unicorn的代碼倉(cāng)庫(kù)??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)
題目來(lái)源
本題來(lái)源為：
Leetcode面試題 08.01. 三步問(wèn)題
題目描述
三步問(wèn)題。有個(gè)小孩正在上樓梯，樓梯有n階臺(tái)階，小孩一次可以上1階、2階或3階。實(shí)現(xiàn)一種方法，計(jì)算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對(duì)結(jié)果模1000000007。
題目解析
我們模擬一下小孩上樓梯的過(guò)程，會(huì)很容易發(fā)現(xiàn)規(guī)律
算法原理
1.狀態(tài)表示
經(jīng)驗(yàn)+題目要求
而經(jīng)驗(yàn)就是：以i位置為結(jié)尾+…
（對(duì)一維的dp而言，基本上就是兩種：以i位置為結(jié)尾+…或者以i位置為開(kāi)始+…）
…表示根據(jù)題目要求進(jìn)行補(bǔ)充完整。
對(duì)于本題而言：
dp[i] 表示:到達(dá)i位置時(shí),一共有多少種方法
2.狀態(tài)轉(zhuǎn)移方程
在推導(dǎo)時(shí)基本上就是：
以i位置的狀態(tài)，最近的一步，來(lái)劃分問(wèn)題
對(duì)于本題而言：到達(dá)i位置需要分三種情況
因此狀態(tài)方程為：
dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
3.初始化
根據(jù)狀態(tài)轉(zhuǎn)移方程：本題為防止越界需要處理下標(biāo)為1,2,3位置的值：
dp[1]=1;
dp[2]=2;
dp[3]=4;
4.填表順序
根據(jù)狀態(tài)轉(zhuǎn)移方程，我們計(jì)算dp[i]位置的值需要i-1與i-2與i-3位置的值，因此我們的填表順序?yàn)椋?strong>從左往右文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-834471.html
5.返回值
根據(jù)題目要求直接返回dp[n]文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-834471.html
代碼實(shí)現(xiàn)
class Solution
{
public:
int waysToStep(int n)
{
// 1.創(chuàng)建dp表
// 2.初始化
// 3.填表
// 4.返回值
const int MOD=1e9+7;
//處理邊界情況：
if(n==1)
return 1;
if(n==2)
return 2;
if(n==3)
return 4;
//創(chuàng)建dp表
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-3]+dp[i-2])%MOD+dp[i-1])%MOD;
}
return dp[n];
}
};
到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃專欄】專題一：斐波那契數(shù)列模型--------2.三步問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
