【動態規劃】--- 斐波那契數模型

?Welcome to 9ilk's Code World

? ? ? ?

(??? ? ???)?個人主頁:? ? ? ?9ilk

(??? ? ???)?文章專欄：? ? ?算法Journey?

🏠 第N個泰波那契數模型

📌 題目解析

第N個泰波那契數

題目要求的是泰波那契數，并非斐波那契數。

📌 算法原理

🎵 遞歸

函數設置：我們可以設置一個Taibo()函數，它能幫我們求出第n個泰波那契數。

函數返回值：題目保證answer <= 2^31 - 1，設置為int即可。

函數實現：根據定義求泰波那契數,我們需要前三個的泰波那契數相加,也就是Taibo(n-3) + Taibo(n-2) + Taibo(n-1)。

函數邊界條件：對于n = 0,1,2是邊界情況，我們可以提前處理。

參考代碼：

class Solution {
public:long Taibo(int n){if(n == 0)return 0;if(n == 1 || n == 2)return 1;return Taibo(n-1) + Taibo(n-2) + Taibo(n-3);}int tribonacci(int n){return Taibo(n);}
};

🎵 記憶化搜索

對于解法一存在下面的問題：

我們發現在遞歸過程有的節點的值(比如上圖的Taibo(3))在第3層就已經求得了，但是其他節點遞歸深入時又重新計算了，導致了不必要的時間和棧空間的開銷(時間復雜度：O(3^n),空間復雜度：O(N))。本題雖然n最大為37，但其實棧空間和時間開銷已經很大了，肯定會超時，我們可以采取記憶化搜索的方法：

1. 添加一個備忘錄。

2. 每次遞歸返回時，將結果放到備忘錄里面。

3. 在每次進入遞歸時，往備忘錄里查詢是否已經記錄。

參考代碼：

class Solution {
public:vector<int> memory;long Taibo(int n){if (memory[n] != -1) //查看備忘錄return memory[n];long ret = Taibo(n - 1) + Taibo(n - 2) + Taibo(n - 3);;memory[n] = ret; //存進備忘錄return ret;}int tribonacci(int n){memory.resize(38, -1); //創建一個備忘錄memory[0] = 0;memory[1] = memory[2] = 1;return Taibo(n);}
};

此時比之前大大避免了不必要的時間開銷，時間復雜度是(n)。

🎵 動態規劃

我們動態規劃分為以下幾步：

1. 狀態表示：

所謂狀態表示其實是dp表里每個值代表的含義。

Q：狀態從何而來？

題目要求(比如本題已經告訴我們要求的是第n個泰波那契數)。
經驗 + 題目要求(后面我們再提)。
分析問題的過程，發現重復的子問題。

因此，本題dp[i]的含義是第i個泰波那契數。

2. 狀態轉移方程：

狀態轉移方程回答的是dp[i]怎么得到的問題，一般我們從"最近一步"得到。

比如本題中，由定義知，在 n >= 0?的條件下 Tn+3?= Tn?+ Tn+1?+ Tn+2，不就是dp[i] = dp[i-1] + dp[i-2] + dp[i-3]嗎？

3. 初始化：

初始化保證我們填表的時候不發生越界！

當遇到n=2時，此時n-3=-1很明顯會會發生越界，因此對于邊界情況，我們可以提前確定好邊界位置在dp表中的值，即dp[0] = 0, dp[1] = dp[2] = 1。

4. 填表順序：

動態規劃需要狀態的推導，只有確定好填表順序，才能確保在填寫當前狀態時，所需要的狀態已經計算過了。

本題很明顯是從左往右填表。

5. 返回值：

我們需要根據題目要求+狀態表示來確定返回值。

注：dp[i]不一定就是我們所需的返回值，我們還需結合題目要求，本題dp[n]就是我們需要的返回值。

參考代碼：

class Solution 
{
public:int tribonacci(int n){//1.狀態表示：dp[i]表示第N個泰波那切數vector<int> dp(38,-1);//2.初始化dp[0] = 0;dp[1] = dp[2] = 1;//3.填表for(int i = 3 ; i <= n ; i ++){dp[i] = dp[i-1] + dp[i-2] + dp[i-3];//4.狀態轉移方程} return dp[n];//5.返回值}
};

時間復雜度：O（N）

空間復雜度：O（1）

🎵 滾動數組

我們用vector容器來模擬dp表，但其實可以進一步優化，當求dp[i]只有前面的若干個狀態，最前面的幾個狀態不需要浪費空間，此時可以使用滾動數組優化！

我們可以利用四個變量來儲存最近一次求泰波那契數的四個狀態，不斷進行滾動，最終求得目標結果！

注：對于賦值順序，不能從右往左賦，即c = d,b = c, a = b因為d給c之后，c被d覆蓋了，但是b想要的是c的，而c原本的值被覆蓋了！

參考代碼：

class Solution 
{
public:int tribonacci(int n){//1.狀態表示：dp[i]表示第N個泰波那切數if (n == 0) return 0;if (n == 1 || n == 2) return 1;int a = 0;int b = 1;int c = 1;int d = 0;//3.填表for (int i = 3; i <= n; i++){d = a + b + c;;//狀態轉移方程a = b;b = c;c = d;}return d;}
};

🏠 三步問題

📌 題目解析

三步問題

📌 算法原理

1. 狀態表示(經驗 + 題目要求)：

狀態表示：dp[i]表示到達i位置時，一共有多少種方法。

2. 狀態轉移方程：

我們從i位置的狀態，最近的一步來劃分問題，由于小孩一次可以上1階，2階，3階：

從i-1位置上來，此時dp[i] += dp[i-1]。
從i-2位置上來，此時dp[i] += dp[i-2]。
從i-3位置上來，此時dp[i] += dp[i-3]。

因此狀態轉移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

3. 初始化：

?對于第1，2，3級的臺階，取它們的最近狀態可能會造成數組越界(比如i為2時，i-3得-1會越界)，因此我們可以提前設置好它們的狀態：dp[1] = 1 , dp[2] = 2，dp[3] = 4。

4. 填表順序：

由狀態轉移方程知，我們i位置的狀態依賴于前幾個位置的狀態，因此我們填表順序是從左往右填。

5.返回值：

我們要求的是上到第n階樓梯的總方法，直接返回dp[n]即可，注意要對結果模1000000007。

參考代碼：

class Solution 
{
public:int waysToStep(int n){if(n == 1 || n == 2) return n;if(n == 3) return 4;long a = 1; //dp[1]long b = 2; //dp[2] long c = 4; //dp[3]long d = 0; for(int i = 4 ; i <= n ; i ++) //空間優化{d = (a + b + c)%1000000007; //狀態轉移方程a = b;b = c;c = d;}      return d;}
};

🏠 最小花費爬樓梯

📌 題目解析

最小花費爬樓梯

假設n為數組元素個數，則本題中樓梯頂部指的是dp[n]，并非dp[n-1]。

📌 算法原理

🎵 解法一 (以i位置為結尾)

1. 狀態表示：

dp[i]表示:到達 i 位置時,所需支付的最少費用。

2. 狀態轉移方程：

用i位置的最近一步(之前或之后的狀態)，推導出dp[i]的值。

當到達i-1位置時，支付cost[i-1],走一步到達i位置 -> dp[i-1] + cost[i-1]。
當到達i-2位置時，支付cost[i-2],走兩步到達i位置 -> dp[i-2] + cost[i-2]。
我們要么選擇從i-1位置到i，要么選擇從i-2位置到i，我們要的是最小花費，則選最小的即可。

因此狀態轉移方程：dp[i] = min(dp[i-1]+cost[i-1] , dp[i-2] + cost[i-2])。

3.初始化

我們需要保證填表的時候不越界，本題可以選擇從下標為0或下標為1的位置開始爬樓梯，因此這兩個位置最初的花費是0，即dp[0] = dp[1] = 0。

4. 填表順序

根據我們的狀態轉移方程，我們需i位置之前的狀態，因此填表順序是從左往右填。

5. 返回值

返回達到樓梯頂部的最低花費,返回dp[n]即可。

參考代碼：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();if(n == 1 || n == 0) return  0;vector<int> dp(n+1);dp[0] = dp[1] = 0 ; //初始化for(int i = 2 ; i <= n ; i ++) {dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}   //狀態轉移方程return dp[n]; //返回值}
};

🎵 解法二?(以i位置為起點)
?

1. 狀態表示：

dp[i]表示:從i位置出發,所需支付的最少費用。

2. 狀態轉移方程：

用i位置的最近一步(之前或之后的狀態)，推導出dp[i]的值。

支付cost[i], 往后走一步,從i+1的位置出發到終點 -> dp[i+1] + cost[i]
支付cost[i], 往后走兩步,從i+2的位置出發到終點 -> dp[i+2] + cost[i]
我們從i位置要么選擇走一步到終點，要么選擇走兩步到終點,我們要的是最小花費，則選最小的即可。

因此狀態轉移方程：dp[i] = min(dp[i+1] + cost[i] , dp[i+2] + cost[i])。

3.初始化

對于n-1位置和n-2位置作為出發點,此時他們走一步或兩步就到頂部了,因此i+1和i+2會使他們越界,我們只需支付他們對應的cost即可,即dp[n-1] = cost[n-1] && dp[n-2] = cost[n-2]。

4. 填表順序

根據我們的狀態轉移方程，我們需i位置之后的狀態，因此填表順序是從右往左填。

5. 返回值

我們是從0或1位置為起點出發的，我們返回兩者最小即可，即min(dp[0],dp[1])。

參考代碼：

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

🏠 解碼方法

📌 題目解析

91. 解碼方法 - 力扣（LeetCode）

本題可能存在無法解碼的字符串。
字符串中可能包含前導0。

📌 算法原理

1.狀態表示：

根據經驗+題目要求，我們可以設置dp[i]的狀態：字符串以i位置結尾時，解碼方法的總數。

2. 狀態轉移方程：

我們還是按照最近一步來劃分問題，對于i位置的解碼我們以下兩種情況：

(1) s[i] 單獨解碼：

解碼成功('1' <= s[i] <= '9',‘0’無法參與解碼),此時解碼總方法等于前一個位置的解碼方法總數，即dp[i-1]。?
解碼失敗，此時為0。

(2) s[i] 與 s[i-1]解碼

解碼成功(0 <= b*10+a <= 26)，時解碼總方法等于第i-2個位結尾字符串的解碼方法總數，即dp[i-2]。?
解碼失敗，此時為0。

因此狀態轉移方程為：dp[i] = dp[i-1] + dp[i-2]

3. 初始化：

(1) i = 0時，位于字符串的第一個字符，我們只需判斷它單獨解碼情況是否成立，取值可能為0，1。

(2) i = 1時，位于字符串的第二個字符，首先要單獨解碼就得先判斷第一個字符能否單獨解碼否則沒意義，能單獨解碼則dp[1]++；再判斷與s[0]是否能解碼，能則dp[1]++。其可能取值為0，1，2。

4. 狀態轉移方程：

根據狀態轉移方程，我們需要之前位置的狀態，因此填表順序是從左往右。

5. 返回值：

由題意得，最終需要的是以size-1為位置結尾的字符串的所有解碼方法，因此返回dp[size-1]。

參考代碼：

class Solution {
public:int numDecodings(string s){int n = s.size();vector<int> dp(n);dp[0] = s[0] != '0';//初始化處理邊界if(n == 1) return dp[0];if(s[0] != '0' && s[1] != '0') dp[1] += 1;//s[1]單獨解碼int t = (s[0]-'0')*10 + s[1] - '0'; if(t >= 10 && t <= 26) dp[1] += 1 ;//s[1]與前一個位置解碼for(int i = 2 ; i < n ; i ++){//一個數編碼if(s[i] != '0') dp[i] += dp[i-1];//兩個數編碼int t = (s[i-1]-'0')*10 + s[i] - '0'; if(t >= 10 && t <= 26) dp[i] += 1;}return dp[n-1];}
};

🎵 優化(虛擬節點)

Q：我們發現這兩段代碼相似度較高，處理邏輯是一樣的，能不能把邊界情況放進循環里處理呢？

這里我們介紹一下虛擬節點：

我們可以在原dp表基礎上擴充一個位置,保證最后一個位置下標為n,這樣在處理字符串中原來下標為0位置的字符時,它在新dp表的下標變為1,這樣i-1就不會越界!但是同時要注意兩個問題:

1. 虛擬節點里面的值,要保證后面的填表時正確的。(比如對于新dp表的0下標位置，我們要保證對于如果字符串第二個位置的字符能跟第一個字符解碼，此時需要新dp表i-2位置的值，也就是dp[0]，此時我們需要設置它為1，表示存在第二個字符和第二個字符共同解碼這一種解碼方法)

2. 下標的映射關系：我們新dp表下標在原來基礎上+1，但是s[i]的size并沒有變化！

class Solution
{
public:int numDecodings(string s)
{
//優化int n=s.size();vector<int>dp(n + 1);dp[0]=1;//保證后面的填表是正確的dp[1]= s[1 - 1] != '0';
注意映射關系s[1-1]下標映射關系for(inti=2;i<=n;i++){if(s[i-1]!='0')dp[i]+=dp[i-1];//處理單獨編碼的情況int =(s[i-2]-'0')*10+s[i-1]-'0';//第二種情況所對應的數if(t>=10 &&t<=26)dp[i]+=dp[i] += dp[i - 2];}return dp[n];
}

完。