目錄
300.最長遞增子序列
動態規劃法
674.最長連續遞增序列
動態規劃法
718.最長重復子數組
動態規劃法
300.最長遞增子序列
-
題目鏈接：300. 最長遞增子序列 - 力扣（LeetCode）
-
文章講解：代碼隨想錄
動態規劃法
-
“子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序”。
-
解題思路
-
子序列問題是動態規劃解決的經典問題，當前下標i的遞增子序列長度，其實和i之前的下表j的子序列長度有關系.
-
-
解題步驟
-
dp[i]的定義：dp[i]表示i之前包括i的以nums[i]結尾的最長遞增子序列的長度
-
狀態轉移方程：位置i的最長升序子序列等于j從0到i-1各個位置的最長升序子序列 + 1 的最大值。所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);注意這里不是要dp[i] 與 dp[j] + 1進行比較，而是我們要取dp[j] + 1的最大值。
-
dp[i]的初始化：每一個i，對應的dp[i]（即最長遞增子序列）起始大小至少都是1.
-
確定遍歷順序：dp[i] 是有0到i-1各個位置的最長遞增子序列 推導而來，那么遍歷i一定是從前向后遍歷。j其實就是遍歷0到i-1，那么是從前到后，還是從后到前遍歷都無所謂，只要吧 0 到 i-1 的元素都遍歷了就行了。 所以默認習慣 從前向后遍歷。
-
舉例推導dp數組：
-
-
代碼注意
-
dp[j] + 1不是和dp[i]比，而是找最大的dp[j] + 1
-
-
代碼一：動態規劃
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取長的子序列}return result;}
};674.最長連續遞增序列
-
題目鏈接：674. 最長連續遞增序列 - 力扣（LeetCode）
-
文章講解：代碼隨想
動態規劃法
-
解題思路
-
本題相對于動態規劃：300.最長遞增子序列 (opens new window)最大的區別在于“連續”。本題要求的是最長連續遞增序列
-
-
解題步驟
-
確定dp數組（dp table）以及下標的含義：dp[i]：以下標i為結尾的連續遞增的子序列長度為dp[i]。注意這里的定義，一定是以下標i為結尾，并不是說一定以下標0為起始位置。
-
確定遞推公式：如果 nums[i] > nums[i - 1]，那么以 i 為結尾的連續遞增的子序列長度 一定等于 以i - 1為結尾的連續遞增的子序列長度 + 1 。即：dp[i] = dp[i - 1] + 1;注意這里就體現出和動態規劃：300.最長遞增子序列 (opens new window)的區別！為本題要求連續遞增子序列，所以就只要比較nums[i]與nums[i - 1]，而不用去比較nums[j]與nums[i] （j是在0到i之間遍歷）。既然不用j了，那么也不用兩層for循環，本題一層for循環就行，比較nums[i] 和 nums[i - 1]。
-
dp數組如何初始化：以下標i為結尾的連續遞增的子序列長度最少也應該是1，即就是nums[i]這一個元素。所以dp[i]應該初始1;
-
確定遍歷順序：從遞推公式上可以看出， dp[i + 1]依賴dp[i]，所以一定是從前向后遍歷。
-
舉例推導dp數組：
-
-
代碼一：動態規劃
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 連續記錄dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};
718.最長重復子數組
-
題目鏈接：718. 最長重復子數組 - 力扣（LeetCode）
-
文章講解：代碼隨想錄
動態規劃法
-
解題思路
-
注意題目中說的子數組，其實就是連續子序列。要求兩個數組中最長重復子數組，如果是暴力的解法 只需要先兩層for循環確定兩個數組起始位置，然后再來一個循環可以是for或者while，來從兩個起始位置開始比較，取得重復子數組的長度。本題其實是動規解決的經典題目，用二維數組可以記錄兩個字符串的所有比較情況，這樣就比較好推 遞推公式了。
-
-
解題步驟
-
確定dp數組（dp table）以及下標的含義：dp[i][j] ：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，最長重復子數組長度為dp[i][j]。 （特別注意： “以下標i - 1為結尾的A” 標明一定是 以A[i-1]為結尾的字符串 。其實dp[i][j]的定義也就決定著，我們在遍歷dp[i][j]的時候i 和 j都要從1開始。
-
確定遞推公式：根據dp[i][j]的定義，dp[i][j]的狀態只能由dp[i - 1][j - 1]推導出來。即當A[i - 1] 和B[j - 1]相等的時候，dp[i][j] = dp[i - 1][j - 1] + 1;根據遞推公式可以看出，遍歷i 和 j 要從1開始！
-
dp數組如何初始化：根據dp[i][j]的定義，dp[i][0] 和dp[0][j]其實都是沒有意義的！但dp[i][0] 和dp[0][j]要初始值，因為 為了方便遞歸公式dp[i][j] = dp[i - 1][j - 1] + 1;所以dp[i][0] 和dp[0][j]初始化為0。舉個例子A[0]如果和B[0]相同的話，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始為0，正好符合遞推公式逐步累加起來。
-
確定遍歷順序：外層for循環遍歷A，內層for循環遍歷B。同時題目要求長度最長的子數組的長度。所以在遍歷的時候順便把dp[i][j]的最大值記錄下來。
-
舉例推導dp數組：
-
-
代碼一：動態規劃
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};
