什么是動(dòng)態(tài)規(guī)劃

線性動(dòng)態(tài)規(guī)劃：是可以用一個(gè)dp表來存儲內(nèi)容，并且找到規(guī)律存儲,按照規(guī)律存儲。讓第i個(gè)位置的值等于題目要求的答案
>dp表：dp表就是用一個(gè)連續(xù)的空間存儲需要存儲的有規(guī)律的值。

干說無力直接正文

正文

力扣題

第 N 個(gè)泰波那契數(shù)

題目:地址
題目解析:

給定了三個(gè)數(shù) T0,T1,T2
求Tn的值
**根據(jù)題意可以翻譯成 Tn = Tn-1+Tn-2+Tn-**3

動(dòng)態(tài)規(guī)則的題目都可以分五步
1、狀態(tài)表示(★)
狀態(tài)表示是必須要會(huì)的并且理解的
>一般的狀態(tài)表示是:經(jīng)驗(yàn)+題目解析
經(jīng)驗(yàn)是要多寫才能得出來的
這個(gè)題目的狀態(tài)表示已經(jīng)給出來了
Tn的值是前三個(gè)值的合
2、狀態(tài)轉(zhuǎn)移方程(★)
狀態(tài)轉(zhuǎn)移方程一般可以表示成 第n個(gè)值=····
題目已經(jīng)給出Tn=Tn-1+Tn-2+Tn-3
3、初始化
把dp表初始化成0
4、填dp表順序
從左往右填
5、返回值
dp[n]

代碼答案：

class Solution {
public:int tribonacci(int n) {if(n==0){return 0;}if(n==1||n==2){return 1;}// vector<int> dp(n+1);// dp[0]=0,dp[1]=1,dp[2]=1;// for(int i =3;i<=n;i++)// {//     dp[i]=dp[i-1]+dp[i-2]+dp[i-3];// }//空間優(yōu)化int a= 0,b=1,c=1,d=0;for(int i =3;i<=n;i++){d=a+b+c;a=b;b=c;c=d;}return d;}
};

三步問題

題目:地址
題目解析:

題目解釋:

這個(gè)小男孩一小子可以走 1層/2層/3層
走到第n層的時(shí)候有多少種方法
如果結(jié)果太大需要%1000000007

動(dòng)態(tài)規(guī)劃的五步走:
1、狀態(tài)表示(★)
這個(gè)題目的狀態(tài)表示是

2、狀態(tài)轉(zhuǎn)移方程(★)
依照上面的解釋
動(dòng)態(tài)方程為Tn = Tn-1+Tn-2+Tn-3
3、初始化
初始化dp表為0
4、存儲dp表的順序
從左往右
5、返回值
dp[n]

代碼:

class Solution {
public:int waysToStep(int n) {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;//空間優(yōu)化int a =1,b=2,c=4,d=0;for(int i = 4 ;i<=n;i++){//dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;d=((a+b)%1000000007+c)%1000000007;a=b;b=c;c=d;}return d;}
};

使用最小花費(fèi)爬樓梯

題目:地址
題目解析:

題目解釋:

一個(gè)人一下可以走1-2步
最少需要花費(fèi)多少體力到樓頂
這里的樓頂不是傳過來的字符串的位置
因?yàn)槿绻莻鬟^來的字符串的位置那么應(yīng)該不用+他的值
但是用例1來說
10直接2步到10應(yīng)該是最快的
但是解釋是15
所以樓頂?shù)奈恢脩?yīng)該在傳過來字符的后一個(gè)位置

五步走:

1、狀態(tài)表示

2、狀態(tài)轉(zhuǎn)移方程
方程是:dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2])
3、初始化
把dp表初始化
4、存入dp表的位置
從做向右
5、返回值
返回dp[i]位置的值

代碼:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+2);for(int i =2;i<=cost.size();i++){dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);}return dp[cost.size()];}
};

總結(jié)

這三個(gè)題的是類似的
都是用前幾個(gè)數(shù)來對比或者相加
可能在解釋的時(shí)候有些不好理解，作者也是剛學(xué)不久，分享一下自己的看法,喜歡的可以點(diǎn)點(diǎn)贊。