目錄

題目鏈接：1143.最長公共子序列

思路

代碼

題目鏈接： 1035.不相交的線

思路

代碼

題目鏈接： 53. 最大子序和

思路

代碼

總結

---

題目鏈接：1143.最長公共子序列

思路

? ? ? ? ①dp數組，dp[i][j]表示[0,i-1]的text1和[0,j-1]的text2最長公共子序列的長度為dp[i][j]

? ? ? ? ②遞推公式，如果當前字符相等則dp[i][j] = dp[i-1][j-1] + 1，否則dp[i][j] = max(dp[i-1][j], dp[i][j-1])

? ? ? ? ③dp數組初始化，dp[i][0]和dp[0][j]都初始化為0，因為和空串的子序列長度一定為0

? ? ? ? ④遍歷順序，從前往后，先遍歷哪個字符串都行

? ? ? ? ⑤推導dp數組

代碼

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int result = 0;vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1, 0));// 第一行和第一列初始化為0，創建dp數組時已經全部初始化為0了，這步可以跳過for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {// 如果前一個字符相等，則累加長度if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}// 如果不相等，則取左和上的最大值else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}// 更新最長公共子序列的長度result = result > dp[i][j] ? result : dp[i][j];}}return result;}
};

題目鏈接：1035.不相交的線

思路

? ? ? ? 兩個字符串分別在上下兩條線上，值相等即可連線，求最大連線數，又要求線不能相交。實際還是求最長公共子序列的長度。

代碼

class Solution {
public:// 求最長公共子序列int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1,vector<int>(nums2.size() + 1, 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;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[nums1.size()][nums2.size()];}
};

題目鏈接：53. 最大子序和

思路

? ? ? ? ①dp數組，dp[i]表示下標為i的最大子序列之和，包括i

? ? ? ? ②遞推公式，dp[i] = max(dp[i-1] + nums[i], nums[i])

? ? ? ? ③dp數組初始化，dp[0] = nums[0]

? ? ? ? ④遍歷順序，正序遍歷

? ? ? ? ⑤推導dp數組

代碼

class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();if (len == 1)return nums[0];vector<int> dp(len, 0);dp[0] = nums[0];int result = dp[0];for (int i = 1; i < len; i++) {dp[i] = max(dp[i - 1] + nums[i], nums[i]);result = result > dp[i] ? result : dp[i];}return result;}
};

總結

? ? ? ? ①理解題意，將題目轉換成熟悉的問題

? ? ? ? ②動規五部曲

? ? ? ? ③該復盤了