莫愁千里路
自有到來風
CSDN 請求進入專欄? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??X
是否進入《C++專欄》?
確定
目錄
?線性dp簡介
斐波那契數(shù)列模型?
第N個泰波那契數(shù)
思路：
代碼測試：
?三步問題
思路：
代碼測試：
最小花費爬樓梯
思路：
代碼測試：
?路徑問題
數(shù)字三角形
思路：
代碼測試：
不同路徑?
思路：
代碼測試：
LIS模型
最長遞增子序列
思路：
代碼測試：
?線性dp簡介
線性DP(Introduction)
線性DP是動態(tài)規(guī)劃問題中的一類問題，指狀態(tài)之間有?線性關(guān)系?的動態(tài)規(guī)劃問題
DP解題套路
<1>根據(jù)題意列出狀態(tài)表示dp表里面的值所代表的含義
分析問題的過程中發(fā)現(xiàn)重復子問題
<2>根據(jù)狀態(tài)表示列出狀態(tài)轉(zhuǎn)移方程dp[i]等于什么
<3>初始化填dp表的時候不能越界訪問
<4>填表順序遞推求解的順序
斐波那契數(shù)列模型?
第N個泰波那契數(shù)
題目鏈接：第N個泰波那契數(shù)
泰波那契序列?Tn?定義如下：?
T0?= 0, T1?= 1, T2?= 1, 且在 n >= 0?的條件下 Tn+3?= Tn?+ Tn+1?+ Tn+2
給你整數(shù)?
n，請返回第 n 個泰波那契數(shù)?Tn?的值。示例 1：
輸入：n = 4 輸出：4 解釋： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4示例 2：
輸入：n = 25 輸出：1389537提示：
0 <= n <= 37- 答案保證是一個 32 位整數(shù)，即?
answer <= 2^31 - 1
思路：
<1>狀態(tài)表示 dp[i]表示第 i 個泰波那契數(shù)的值 <2>狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]? (Tn+3?= Tn?+ Tn+1?+ Tn+2) <3>初始化 dp[0] = 0，dp[1] = dp[2] = 1 <4>填表順序 從左至右
代碼測試：
時間復雜度O(N)
空間復雜度O(N)
class Solution { public: int tribonacci(int n) { //防止數(shù)組越界 if(n == 0) return 0; if(n == 1||n == 2) return 1; vector<int> dp(n+1); //初始化 dp[0] = 0,dp[1] = dp[2] = 1; //順序填表 for(int i = 3;i<=n;i++) //狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]; return dp[n]; } };
?三步問題
題目鏈接：三步問題
三步問題。有個小孩正在上樓梯，樓梯有n階臺階，小孩一次可以上1階、2階或3階。實現(xiàn)一種方法，計算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對結(jié)果模1000000007。
示例1:
輸入：n = 3 輸出：4 說明: 有四種走法示例2:
輸入：n = 5 輸出：13提示:
- n范圍在[1, 1000000]之間
思路：
我們發(fā)現(xiàn)從 4 層開始就是前三項之和，第五層就是：7 + 4 + 2= 13
所以從第四層開始，滿足斐波那契規(guī)律
<1>狀態(tài)表示 以 i 為結(jié)尾，dp[i]表示到達?i 位置時，一共有多少種方法 <2>狀態(tài)轉(zhuǎn)移方程 以 i 的位置的狀態(tài)，最近的一步開始劃分問題
從(i-1)到 i：dp[i-1]
從(i-2)到 i：dp[i-2]
從(i-3)到 i：dp[i-3]
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
<3>初始化 dp[1] = 1，dp[2] = 2，dp[3] = 4 <4>填表順序 從左往右 代碼測試：
時間復雜度O(N)
空間復雜度O(N)
class Solution { public: int waysToStep(int n) { //取模數(shù)據(jù) const int MOD = 1e9+7; //邊界問題 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; //順序填表 for(int i = 4;i<=n;i++) //狀態(tài)轉(zhuǎn)移方程+取模操作 dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD; return dp[n]; } };
最小花費爬樓梯
題目鏈接：最小花費爬樓梯
數(shù)組的每個下標作為一個階梯，第?
i?個階梯對應(yīng)著一個非負數(shù)的體力花費值?cost[i]（下標從?0?開始）。每當爬上一個階梯都要花費對應(yīng)的體力值，一旦支付了相應(yīng)的體力值，就可以選擇向上爬一個階梯或者爬兩個階梯。
請找出達到樓層頂部的最低花費。在開始時，你可以選擇從下標為 0 或 1 的元素作為初始階梯。
示例?1：
輸入：cost = [10, 15, 20] 輸出：15 解釋：最低花費是從 cost[1] 開始，然后走兩步即可到階梯頂，一共花費 15 。?示例 2：?
輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 輸出：6 解釋：最低花費方式是從 cost[0] 開始，逐個經(jīng)過那些 1 ，跳過 cost[3] ，一共花費 6 。提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路：
由題意可知：我們的樓層頂部并不是數(shù)組的末元素，而是末元素的下一位
?
<1>狀態(tài)表示 以 i 為結(jié)尾，dp[i]表示到達?i 位置時，最小花費 <2>狀態(tài)轉(zhuǎn)移方程 使用之前或者之后的狀態(tài)，推導出dp[i]的值
根據(jù)最近的一步來劃分問題
(1)先到達 i-1 的位置，然后支付cost[i-1]，走一步：dp[i-1]+cost[i-1]
(2)先到達 i-2 的位置，然后支付cost[i-2]，走二步：dp[i-2]+cost[i-2]
dp[i] = min(dp[i-1]+cost[i-1]，dp[i-2]+cost[i-2])
<3>初始化 由題意?你可以選擇從下標為 0 或 1 的元素作為初始階梯 得：
dp[0] = dp[1] = 0
<4>填表順序 從左往右 <5>返回值 dp[n]
代碼測試：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { //計算數(shù)組長度 int n = cost.size(); vector<int> dp(n+1); //初始化 dp[0] = dp[1] = 0; //順序填表 for(int i = 2;i<=n;i++) //狀態(tài)轉(zhuǎn)移方程 dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); return dp[n]; } };
?路徑問題
數(shù)字三角形
題目鏈接：數(shù)字三角形
題目描述#
觀察下面的數(shù)字金字塔
寫一個程序來查找從最高點到底部任意處結(jié)束的路徑，使路徑經(jīng)過數(shù)字的和最大。每一步可以走到左下方的點也可以到達右下方的點。
在上面的樣例中，從?7→3→8→7→5 的路徑產(chǎn)生了最大權(quán)值。
輸入格式#
第一個行一個正整數(shù)?r?表示行的數(shù)目。
后面每行為這個數(shù)字金字塔特定行包含的整數(shù)。
輸出格式#
單獨的一行,包含那個可能得到的最大的和。
輸入輸出樣例#
輸入 #1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5輸出 #1
30
思路：
在看到數(shù)字三角形的構(gòu)造時，我們首先想到用 二維數(shù)組 來存放整個三角形（行與列）
也許有人會想到 貪心算法 來實現(xiàn)，但是貪心算法在這里是不適用的
貪心只注重眼前的利益（如上圖），貪心策略算出的數(shù)字的和是：28 不符合我們的最大值
所以眼光放長，我們要的是最后的數(shù)字和最大，嘗試用 動態(tài)規(guī)劃 解決問題
注意：
我們發(fā)現(xiàn)從上面往下一步步走很麻煩，直接搜索肯定超時
所以我們的切入點是 由下至上 的回溯，依層次更換改動大值，回到頂端時，就是結(jié)果
例如：
我們找到倒數(shù)第二排的元素 2 ，此時只有兩種方法可以走，左下方或者右下方
我們要保證數(shù)字和最大，所以必然選擇 右下方 ，這個時候的較大值為 7
同理：我們考慮倒數(shù)第二排的元素 7 ，較大值為 12
依次類推則倒數(shù)第二排變?yōu)椋?/p>
7 12 10 10因為我們的倒數(shù)第二排已經(jīng)包含了最后一排的最優(yōu)解，所以我們的三角形可以簡化成：
7 3 8 8 1 0 7 12 10 10方法同上我們找到倒數(shù)第二排的元素 8 ，再比較走兩條路的值，右邊的值更大，選擇右邊的值，所以這個時候的較大值為 20
以此類推，得到下面的數(shù)字三角形：
7 3 8 20 13 107 23 2130 23 21 20 13 10 7 12 10 10 4 5 2 6 5最后得到我們的最大數(shù)字之和為 30
所以我們的最佳路徑是：7→3→8→7→5
思路我們已經(jīng)理清了，接下來開始推導我們的狀態(tài)轉(zhuǎn)移方程：
<1>狀態(tài)表示 以 [i，j] 為結(jié)尾，dp[ i ][ j ]表示到達 [i，j] 位置時，最大的數(shù)字之和 <2>狀態(tài)轉(zhuǎn)移方程 dp[i][j]+=max(dp[i+1][j]，dp[i+1][j+1])
<3>初始化 按要求輸入
<4>填表順序 從下至上，從左至右 <5>返回值 dp[1][1] <6>小總結(jié) 畫圖求解，發(fā)現(xiàn)規(guī)律，列出狀態(tài)轉(zhuǎn)移方程
代碼測試：
#include<bits/stdc++.h> using namespace std; int main() { int n = 0;cin>>n; vector<vector<int>> dp((n+1),vector<int>(n+1)); //初始化 for(int i = 1;i<=n;i++) for(int j = 1;j<=i;j++) cin>>dp[i][j]; //順序填表 for(int i = n-1;i>=1;i--) for(int j = 1;j<=i;j++) //狀態(tài)轉(zhuǎn)移方程 dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]); //返回值 cout<<dp[1][1]<<endl; return 0; }
不同路徑?
?題目鏈接：不同的路徑
一個機器人位于一個?
m x n?網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角
（在下圖中標記為 “Finish” ）。
問總共有多少條不同的路徑？
示例 1：
輸入：m = 3, n = 7 輸出：28示例 2：
輸入：m = 3, n = 2 輸出：3 解釋： 從左上角開始，總共有 3 條路徑可以到達右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：
輸入：m = 7, n = 3 輸出：28示例 4：
輸入：m = 3, n = 3 輸出：6提示：
1 <= m, n <= 100- 題目數(shù)據(jù)保證答案小于等于?
2 * 10^9
思路：
二維dp
狀態(tài)轉(zhuǎn)移方程的得出
初始化問題
為了防止數(shù)組越界，所以我們要考慮 dp 的初始化問題
注意：
<1>然后在考慮虛擬位置的值，要保證我們后面填表的結(jié)果是正確的
<2>二維數(shù)組的行和列都要加一（加上了虛擬位置）
我們只要將 dp[0][1] 或者 dp[0][1] 的位置初始化為 1 就可以了?
<1>狀態(tài)表示 以[i，j]為結(jié)尾時，dp[i][j]表示走到[i，j]的位置，一共有多少種方式 <2>狀態(tài)轉(zhuǎn)移方程 dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1]
<3>初始化 dp[0][1] = 1 <4>填表順序 從左至右，從上至下 <5>返回值 dp[m][n] 代碼測試：
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m+1,vector<int>(n+1)); //初始化 dp[0][1] = 1; //順序填表 for(int i = 1;i<=m;i++) for(int j = 1;j<=n;j++) //狀態(tài)轉(zhuǎn)移方程 dp[i][j] = dp[i-1][j]+ dp[i][j-1]; //返回值 return dp[m][n]; } };
LIS模型
最長遞增子序列
題目鏈接：最長遞增子序列
給你一個整數(shù)數(shù)組?
nums?，找到其中最長嚴格遞增子序列的長度。子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，
?[3,6,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子序列。示例 1：
輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。示例 2：
輸入：nums = [0,1,0,3,2,3] 輸出：4示例 3：
輸入：nums = [7,7,7,7,7,7,7] 輸出：1
思路：
子序列的介紹：
子序列指的是一個序列中，按照原順序選出若干個 一定連續(xù) 的元素所組成的序列
狀態(tài)轉(zhuǎn)移方程的推理：
初始化：將dp標準的狀態(tài)成最壞的情況，最后更新dp表就可以了
填表順序：因為我們要填 dp[i] 就要用到前面的值，所以是：從左往右
注意：要判斷 nums[j]<nums[i]文章來源：http://www.zghlxwxcb.cn/news/detail-825899.html
<1>狀態(tài)表示 dp[i]表示以 i 位置為結(jié)尾的所有子序列中，最長遞增子序列的長度 <2>狀態(tài)轉(zhuǎn)移方程 dp[i] = max(dp[i]+1,dp[i])文章來源地址http://www.zghlxwxcb.cn/news/detail-825899.html
<3>初始化 dp表中所有元素都置為1 <4>填表順序 從左往右 <5>返回值 dp表中的最大值 代碼測試：
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); //初始化 vector<int> dp(n,1); int ret = 1; //順序填表 for(int i = 1;i<n;i++) { for(int j = 0;j<i;j++) //前提條件 if(nums[j]<nums[i]) //狀態(tài)轉(zhuǎn)移方程 dp[i] = max(dp[j]+1,dp[i]); ret = max(ret,dp[i]); } //返回值 return ret; } };
到了這里，關(guān)于C++動態(tài)規(guī)劃-線性dp算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
