堅(jiān)持就是勝利 - -?
文章目錄
1.第N個(gè)泰波那切數(shù)
2.三步問(wèn)題
3.使用最小花費(fèi)爬樓梯
4.解碼方法
1.第N個(gè)泰波那切數(shù)
力扣鏈接：力扣
泰波那契序列?Tn?定義如下：?
T0?= 0, T1?= 1, T2?= 1, 且在 n >= 0?的條件下 Tn+3?= Tn?+ Tn+1?+ Tn+2
給你整數(shù)?n，請(qǐng)返回第 n 個(gè)泰波那契數(shù)?Tn?的值。
?首先我們分析一下題目，在n>=0的條件下也就是說(shuō)都是正數(shù)，然后給了一個(gè)算泰博納妾數(shù)的公式，這道題很簡(jiǎn)單，但是我們還是一步步帶著大家來(lái)分析：
首先在我們以后做動(dòng)態(tài)規(guī)劃的題，都按照一下這個(gè)模板來(lái)編寫(xiě)：
1.狀態(tài)表示
首先我們先把公式重新推導(dǎo)一下，讓每邊減3得到Tn = Tn-3 + Tn-2 + Tn-1 ，Tn就是第n個(gè)泰博納妾數(shù)，根據(jù)前三個(gè)泰波納妾數(shù)推導(dǎo)出來(lái)的第n個(gè)，所以說(shuō)dp[i]的狀態(tài)就是第i個(gè)泰波納妾數(shù)
2.狀態(tài)轉(zhuǎn)移方程
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]? ? 因?yàn)榈趇個(gè)泰波納妾數(shù)等于前三個(gè)泰波納妾數(shù)的和，所以轉(zhuǎn)移方程就是這個(gè)
3.初始化
我們初始化的目的是為了防止越界，如下圖：
第0個(gè)泰波那切數(shù)的前三個(gè)都是非法的，所以我們必須給定第0個(gè)泰波納妾數(shù)，同理dp[1]和dp[2]同樣會(huì)越界，而題目又貼心的給了我們初始值，dp[0] = 0,dp[1] = 1,dp[2] = 1?
4.填表以及確定填表順序
因?yàn)槲覀兪侵雷筮叺闹担揽孔筮叺闹低瞥鰜?lái)右邊的值，所以順序是從左向右
5.返回值
既然讓我們返回第n個(gè)泰波納妾數(shù)，而我們的狀態(tài)表示dp[i]就表示第i個(gè)泰波納妾數(shù)，所以返回dp[n]就是第n個(gè)泰波納妾數(shù)
思路理解了我們直接寫(xiě)代碼：
class Solution {
public:
int tribonacci(int n) {
//1.創(chuàng)建dp表
//因?yàn)槭菑?開(kāi)始的所以要多開(kāi)一個(gè)位置
vector<int> dp(n+1);
//處理邊界條件
if (n==0) return 0;
if (n==1||n==2) return 1;
//2.初始化
dp[0] = 0,dp[1] = dp[2] = 1;
//3.狀態(tài)轉(zhuǎn)移方程
for (int i = 3;i<=n;i++)
{
dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
}
//返回值
return dp[n];
}
};?首先創(chuàng)建dp表，由于是從0開(kāi)始的所以要多開(kāi)一個(gè)位置存儲(chǔ)第n個(gè)泰波納妾數(shù)，所以空間大小為n+1，因?yàn)榈?個(gè)，第1個(gè)，第2個(gè)泰波那切數(shù)都給出來(lái)了，所以我們只需要從第3個(gè)泰波那切數(shù)開(kāi)始計(jì)算，然后我們處理邊界條件，如果不處理那么數(shù)組會(huì)直接越界，最后返回dp[n]即可。?
下面我們?cè)僦v解一下用滾動(dòng)數(shù)組優(yōu)化的方式，在上面的代碼中我們要求第n個(gè)太波那契數(shù)列數(shù)是沒(méi)必要將n之前的所有泰波那契數(shù)都保存的，我們只需要保存前三個(gè)就可以算出來(lái)了，所以我們只需要用四個(gè)變量就能解決這個(gè)問(wèn)題：
?一開(kāi)始d是第3個(gè)泰波那契數(shù)，經(jīng)過(guò)滾動(dòng)后下一次d變成了第4個(gè)泰波那契數(shù)，下面我們實(shí)現(xiàn)一下代碼：
class Solution {
public:
int tribonacci(int n) {
//初始化前3個(gè)泰波那契數(shù)
int a = 0;
int b = 1;
int c = 1;
int d = 0;
if (n==0) return 0;
if (n==1||n==2) return 1;
for (int i = 3;i<=n;i++)
{
d= a+b+c;
a = b;
b = c;
c = d;
}
return d;
}
};?需要注意的是：滾動(dòng)的時(shí)候應(yīng)該是a向d去依次賦值，不能反過(guò)來(lái)反過(guò)來(lái)會(huì)導(dǎo)致原本c的值被覆蓋。
2.三步問(wèn)題
力扣鏈接：力扣
三步問(wèn)題。有個(gè)小孩正在上樓梯，樓梯有n階臺(tái)階，小孩一次可以上1階、2階或3階。實(shí)現(xiàn)一種方法，計(jì)算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對(duì)結(jié)果模1000000007。
?首先題目說(shuō)有n階臺(tái)階，小孩一次可以上1階或者2階或者3階，然后求有多少種上樓的方式，然后還說(shuō)了題目結(jié)果會(huì)很大需要取模，下面我們就演示一下上樓梯的步驟：
?首先從地平線到第一個(gè)臺(tái)階只有一種方法，所以第一個(gè)臺(tái)階的方法數(shù)就是1.
到達(dá)第二個(gè)臺(tái)階可以從第0個(gè)臺(tái)階跨越2步到達(dá)（這是一種方法），也可以從第一個(gè)臺(tái)階跨越1步到達(dá)，由于要想從第一個(gè)臺(tái)階到第二個(gè)臺(tái)階就得先到第一個(gè)臺(tái)階，而到達(dá)第一個(gè)臺(tái)階的方法數(shù)是1，所以從第一個(gè)臺(tái)階到達(dá)第二個(gè)臺(tái)階的方法數(shù)為1*1==1.所以到達(dá)第二個(gè)臺(tái)階的總次數(shù)為2
到達(dá)第三個(gè)臺(tái)階可以直接從第0個(gè)臺(tái)階跨越3步到達(dá)，也可以從第一個(gè)臺(tái)階跨越2步到，還可以從第二個(gè)臺(tái)階跨越1步到達(dá)。首先從第0個(gè)臺(tái)階跨越3步到達(dá)方法數(shù)是1，從第一個(gè)臺(tái)階跨越需要知道到達(dá)第一個(gè)臺(tái)階的方法數(shù)所以是1*1==1，從第二個(gè)臺(tái)階跨越1步到達(dá)首先要計(jì)算到達(dá)第二個(gè)臺(tái)階的方法數(shù)所以是2*1 == 2，所以總次數(shù)為1 + 1 + 2 = 4.
到達(dá)第4個(gè)臺(tái)階可以從第一個(gè)臺(tái)階直接跨越3步，也可以從第二個(gè)臺(tái)階跨越2步，也可以從第3個(gè)臺(tái)階跨越一步。第一個(gè)臺(tái)階直接跨越3步的方法數(shù)為：1*1==1，第二個(gè)臺(tái)階跨越2步的方法數(shù)為2*1==2，第3個(gè)臺(tái)階跨越一步的方法數(shù)為4*1==4，所以總方法數(shù)為1+2+4==7
下面我們直接套模板：
1.狀態(tài)表示
我們可以看到如果是第5個(gè)臺(tái)階的話那么有13種方法，而我們創(chuàng)建一個(gè)dp表將每個(gè)臺(tái)階的方法數(shù)放入，如下圖：
所以dp[i]就表示第i個(gè)臺(tái)階的方法數(shù)。?
2.狀態(tài)轉(zhuǎn)移方程
可以通過(guò)圖看到，第5個(gè)臺(tái)階的方法數(shù)是前3個(gè)臺(tái)階的方法數(shù)之和，所以狀態(tài)轉(zhuǎn)移方程為：
dp[i] = dp[i-1]? + dp[i-2] + dp[i-3]
3.初始化
由于第0,1,2個(gè)臺(tái)階會(huì)越界，所以我們直接給出方法數(shù)：dp[0] = 1,dp[1] = 1,dp[2] = 2,這里可能有人會(huì)有疑問(wèn)，為什么到達(dá)地平線還有1個(gè)方法呢？在這里我們只能說(shuō)要算第3個(gè)臺(tái)階的方法數(shù)dp[0]必須給1，這是靠分析題目得出來(lái)的。
4.填表
從左向右填表
5.返回值
dp[i]表示第i個(gè)臺(tái)階的方法數(shù)，所以返回dp[n]即可。
class Solution {
public:
int waysToStep(int n) {
const int MOD = 1e9+7;
//創(chuàng)建dp表
vector<int> dp(n+1);
//解決邊界問(wèn)題
if (n==0||n==1) return 1;
if (n==2) return 2;
dp[0] = 1,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];
}
};本題需要注意的是要對(duì)每次求出的臺(tái)階數(shù)取模，否則就會(huì)越界，我們直接用變量保存將要取模的數(shù)
然后在計(jì)算結(jié)果時(shí)每次相加就取模一次。
3.使用最小花費(fèi)爬樓梯
力扣鏈接：力扣
給你一個(gè)整數(shù)數(shù)組?cost?，其中?cost[i]?是從樓梯第?i?個(gè)臺(tái)階向上爬需要支付的費(fèi)用。一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺(tái)階。
你可以選擇從下標(biāo)為?0?或下標(biāo)為?1?的臺(tái)階開(kāi)始爬樓梯。
請(qǐng)你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)。
?這道題有一個(gè)隱含條件，直接看實(shí)例1，我們大多數(shù)人都會(huì)認(rèn)為樓頂就是數(shù)組的最后一個(gè)位置也就是20的位置，如果是20那么答案應(yīng)該是10才對(duì)，為什么是15呢？因?yàn)闃琼斊鋵?shí)是在數(shù)組最后一個(gè)位置的下一個(gè)位置：
了解了這個(gè)后我們講一下如何計(jì)算：
首先能到達(dá)頂樓的位置有兩個(gè)，要不然是頂樓-1的位置，要不然就是頂樓-2的位置，因?yàn)轭}目已經(jīng)告訴了每次只能爬一個(gè)臺(tái)階或者兩個(gè)臺(tái)階。所以我們只需要求出頂樓-1位置的最小花費(fèi)和頂樓-2位置的最小花費(fèi)的較小值，我們以實(shí)例1為例：
?由于題目已經(jīng)告訴從0或1開(kāi)始爬樓梯，所以到達(dá)0位置和1位置的最小花費(fèi)是0.15是第一個(gè)臺(tái)階到達(dá)第一個(gè)臺(tái)階最小花費(fèi)是0，然后15跨兩步到樓頂需要支付15，所以15->樓頂?shù)淖钚』ㄙM(fèi)是15.
要計(jì)算20這個(gè)臺(tái)階的最小花費(fèi)就要先知道哪兩個(gè)臺(tái)階能到20這個(gè)位置，很明顯從第0個(gè)臺(tái)階跨兩步到20，到達(dá)第0個(gè)臺(tái)階的花費(fèi)為0，從第0個(gè)臺(tái)階到第2個(gè)臺(tái)階的花費(fèi)為10，所以10->20的花費(fèi)為10，同理15->20的花費(fèi)為15，那么到臺(tái)階2的最小花費(fèi)就是10，然后從20->樓頂?shù)幕ㄙM(fèi)是20,所以20->樓頂?shù)淖钚』ㄙM(fèi)是10+20==30。
取樓頂-1臺(tái)階的最小值和樓頂-2臺(tái)階的最小值相比較，最小的就是到樓頂?shù)淖钚≈?，所以剛剛的?shí)例2答案為15.
1.狀態(tài)表示
dp[i]表示到達(dá)第i個(gè)臺(tái)階的最小花費(fèi)
2.狀態(tài)轉(zhuǎn)移方程
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.初始化
因?yàn)轭}目告訴了從第0個(gè)臺(tái)階或者第1個(gè)臺(tái)階開(kāi)始爬，所以之前到達(dá)0或1臺(tái)階的最小花費(fèi)是0，所以dp[0]和dp[1]都等于0
4.填表
5.返回值
由于數(shù)組是從0開(kāi)始的，size()的大小就是樓頂?shù)奈恢?，所以返回dp[size()]即可。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
if (cost.size()<=0)
{
return 0;
}
//創(chuàng)建dp表
int sz = cost.size();
vector<int> dp(sz+1);
//初始化
dp[0] = dp[1] = 0;
for (int i = 2;i<=sz;i++)
{
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[sz];
}
};?上面我們是按照從前往后推的下面我們也可以換一個(gè)思想，從后往前推：
?比如我們現(xiàn)在在第7個(gè)臺(tái)階，那么我們支付了第7個(gè)臺(tái)階的費(fèi)用后可以向后走一步也可以走兩步，走一步到第8個(gè)臺(tái)階，第8個(gè)臺(tái)階花費(fèi)100直接能到樓頂。走兩步到第9個(gè)臺(tái)階，花費(fèi)1直接就能到樓頂，這個(gè)時(shí)候我們第7個(gè)臺(tái)階到達(dá)樓頂?shù)淖钚』ㄙM(fèi)就是：第8個(gè)臺(tái)階和第9個(gè)臺(tái)階到達(dá)樓頂?shù)淖钚』ㄙM(fèi)的最小值，所以第7個(gè)臺(tái)階的最小花費(fèi)就是1+1（+1是因?yàn)樽约褐Ц读速M(fèi)用要向后跳），以此類(lèi)推從第7個(gè)臺(tái)階推到第0個(gè)臺(tái)階，又因?yàn)槲覀兪菑?或1出發(fā)，所以最后的返回值是0位置和1位置最小花費(fèi)的最小值。
1.狀態(tài)表示
dp[i]表示從i位置支付費(fèi)用后到達(dá)樓頂花費(fèi)的最小值
2.狀態(tài)轉(zhuǎn)移方程
dp[i] = min(dp[i+1],dp[i+2]) + cost[i]? ?(要記住我們從i位置起跳是需要花錢(qián)的所以要加上cost[i]）
3.初始化
可以看到我們的轉(zhuǎn)移方程是i+1和i+2，所以在距離樓頂?shù)?個(gè)位置和1個(gè)位置的臺(tái)階是無(wú)法計(jì)算的因?yàn)樵浇缌?，并且從這兩個(gè)位置起跳到樓頂只需要花費(fèi)自身cost的費(fèi)用。所以dp[樓頂-1] = cost[樓頂-1],dp[樓頂-2] = cost[樓頂-2]
4.填表
從右向左填表：
5.返回值
返回dp[0]和dp[1]的較小值
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//創(chuàng)建dp表
int sz = cost.size();
vector<int> dp(sz);
//初始化
dp[sz-1] = cost[sz-1];
dp[sz-2] = cost[sz-2];
for (int i = sz-3;i>=0;i--)
{
dp[i] = min(dp[i+1],dp[i+2]) + cost[i];
}
return min(dp[0],dp[1]);
}
};4.解碼方法
力扣鏈接：力扣
?首先我們要能讀懂題，我們做的是解碼工作，題目會(huì)給我們一個(gè)數(shù)字字符串，然后我們可以有多少種方法將數(shù)字轉(zhuǎn)化為不同的字符順序，要注意的是一旦有0作為前導(dǎo)就會(huì)解碼失敗，可以看實(shí)例3。（但是如果是兩個(gè)字符，比如10那么可以解碼為K那么就是一種方法）.首先題目要求字符串的解碼總數(shù)，那我們根據(jù)經(jīng)驗(yàn)就可以得出狀態(tài)表示，解碼總數(shù)就是以字符串最后一個(gè)字符為結(jié)尾的總解碼數(shù)。
1.狀態(tài)表示
dp[i]表示以i字符為結(jié)尾的總解碼數(shù)
2.狀態(tài)轉(zhuǎn)移方程
首先我們要知道dp[i]的方法數(shù)就要看s[i]這個(gè)字符能否解碼，如果這個(gè)字符>='1'并且<='9'那么就是可以解碼的，一旦這個(gè)字符可以解碼就說(shuō)明總方法數(shù)是dp[i-1]，如下圖：
?比如上圖中dp[i]有三種方法分別是abc,acb,cba，當(dāng)s[i]可以解碼時(shí)就可以放在他們的后面，但是方法還是3種，因?yàn)槲覀円蟮氖且詉為結(jié)尾的方法數(shù)而不是字符個(gè)數(shù)！當(dāng)s[i]為0時(shí)那么在前面的所有努力都白費(fèi)了，直接dp[i]等于0
當(dāng)我們的s[i]可以和s[i-1]相結(jié)合變成一個(gè)新的字符時(shí)，那么就可以把s[i]和s[i-1]看成一個(gè)字符，那么總方法數(shù)就是前面i-2的方法數(shù)，所以是dp[i-2]
3.初始化
狀態(tài)轉(zhuǎn)移方程中只有0和1位置會(huì)越界，所以初始化0和1
首先如果第一個(gè)字符是>='1'&&<='9'，那么dp[0]就是1，否則就是0
如果第2個(gè)字符可以解碼，那么方法數(shù)就是i-1的方法數(shù)那就是1，如果第二個(gè)字符還可以和第一個(gè)字符結(jié)合，那么方法數(shù)就變成2
4.填表
已知0和1位置，所以從左向右填表：
5.返回值
返回以字符串最后一個(gè)字符為結(jié)尾的總方法數(shù)
class Solution {
public:
int numDecodings(string s) {
//創(chuàng)建dp表
int sz = s.size();
vector<int> dp(sz,0);
//初始化
dp[0] = s[0]!='0';
//解決邊界條件
if (dp[0]==0) return 0;
if (sz==1) return dp[0];
//初始化
if (s[1]>='1'&&s[1]<='9')
{
dp[1] = 1;
}
int t = (s[0]-'0')*10 + s[1]-'0';
if (t>=10&&t<=26)
{
++dp[1];
}
for (int i = 2;i<sz;i++)
{
if (s[i]>='1'&&s[i]<='9')
{
dp[i] += dp[i-1];
}
int t = (s[i-1]-'0')*10+s[i]-'0';
if (t>=10&&t<=26)
{
dp[i] += dp[i-2];
}
}
return dp[sz-1];
}
};?需要注意的是如果s[0]為0那么是不能解碼的，當(dāng)字符串長(zhǎng)度為1時(shí)要返回dp[0]也就是第一個(gè)字符的方法數(shù)，否則我們下面的初始化dp[1]會(huì)越界。
下面我們講一下能優(yōu)化初始化的思路：
我們可以給dp表多開(kāi)一個(gè)空間，這個(gè)位置放的值要視情況而定，如下圖：
?我們?cè)谠萪p表的基礎(chǔ)上多開(kāi)了一個(gè)位置，那么這個(gè)位置該放多少呢？首先我們知道，第一個(gè)字符是一定要初始化的，第一個(gè)字符對(duì)應(yīng)的dp表的位置再dp[1]，我們將這個(gè)位置初始化使用動(dòng)態(tài)轉(zhuǎn)移方程的時(shí)候才不會(huì)越界（只要滿足i-1,i-2不越界），dp[1]是我們自己初始化的，dp[2]需要狀態(tài)轉(zhuǎn)移方程計(jì)算，當(dāng)?shù)诙€(gè)字符可以解碼那么方法數(shù)是dp[i-1]也就是第一個(gè)字符的方法數(shù)1，然后第二個(gè)字符還可以和第一個(gè)字符結(jié)合，一旦結(jié)合解碼數(shù)就變成dp[i-2]，而dp[i-2]是我們的虛擬位置，如果我們第一個(gè)虛擬位置初始化為0，計(jì)算dp[i-2]的時(shí)候就會(huì)少一個(gè)方法數(shù)，所以1才是正確的，我們也可以再舉一個(gè)例子：
?拿"2 0"來(lái)說(shuō)，0位置的方法數(shù)是dp[i-1]+dp[i-2]，由于是0所以dp[i-1]是0，dp[i-2]是我們的虛擬位置，2和0是可以結(jié)合的所以要有一種方法，如果虛擬位置為0就是0種方法就錯(cuò)了，所以虛擬位置應(yīng)該為1.有了虛擬位置那么計(jì)算對(duì)應(yīng)的字符串都需要-1，原來(lái)-1的要變成-2的字符，比如dp[i]的方法數(shù)是s[i-1]位置的字符的方法數(shù)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-464090.html
class Solution {
public:
int numDecodings(string s) {
//創(chuàng)建dp表
int sz = s.size();
vector<int> dp(sz+1,0);
//初始化
dp[0] = 1;
dp[1] = s[0]!='0';
for (int i = 2;i<=sz;i++)
{
if (s[i-1]>='1'&&s[i-1]<='9')
{
dp[i] += dp[i-1];
}
int t = (s[i-2]-'0')*10+s[i-1]-'0';
if (t>=10&&t<=26)
{
dp[i] += dp[i-2];
}
}
return dp[sz];
}
};可以看到此方法不僅簡(jiǎn)化了代碼而且讓我們的初始化變的更簡(jiǎn)單。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-464090.html
到了這里，關(guān)于60題學(xué)會(huì)動(dòng)態(tài)規(guī)劃系列：動(dòng)態(tài)規(guī)劃算法第一講的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
