題目1：1143? 最長公共子序列

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

對題目的理解

返回兩個字符串的最長公共子序列的長度，如果不存在公共子序列，返回0，注意返回的是最長公共子序列，與前一天的最后一道題不同的是子序列是可以不連續(xù)的

動態(tài)規(guī)劃

動規(guī)五部曲

1）dp數(shù)組及下標i的含義

dp[i][j]：以[0,i-1]的nums1和以[0,j-1]的nums2的最長公共子序列的長度

2）遞推公式

主要是兩種情況，1）元素相同；2）元素不同

3）dp數(shù)組初始化

dp[i][0]和dp[0][j]? 無意義，但是為了遞推公式的需要，均初始化為0，其余下標位置處的數(shù)值初始化為任意值均可，但是為了方便起見，均初始化為0。

4）遍歷順序

根據(jù)遞推公式，由左往右推導遍歷，從上到下推導遍歷。

5）打印dp數(shù)組

最終結果在dp[num1.size()][nums2.size()]

代碼

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//定義并初始化dp數(shù)組vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,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]);}}return dp[text1.size()][text2.size()];}
};

• 時間復雜度: O(n * m)，其中 n 和 m 分別為 text1 和 text2 的長度
• 空間復雜度: O(n * m)

題目2：1035? 不相交的線

題目鏈接：不相交的線
對題目的理解

連接數(shù)組nums1和nums2中的相同數(shù)字代表的點，每條直線不能相交，計算最大連線數(shù)

直線不能相交，這就是說明在字符串A中找到一個與字符串B相同的子序列，且這個子序列不能改變相對順序，只要相對順序不改變，連接相同數(shù)字的直線就不會相交。

本題就是套了一層連線的外殼，代碼與上一道題一模一樣，就是找兩個數(shù)組中存在的最大相同子序列的長度。

分析過程與上一道題一模一樣

代碼

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {//定義并初始化dp數(shù)組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()];}
};

• 時間復雜度: O(n * m)
• 空間復雜度: O(n * m)

題目3：53? 最大子序和

題目鏈接：最大子序和

對題目的理解

找出具有最大和的連續(xù)子數(shù)組（至少包含一個元素），返回最大和，注意子數(shù)組是連續(xù)的

貪心算法

局部最優(yōu)：當前“連續(xù)和”為負數(shù)的時候立刻放棄，從下一個元素重新計算“連續(xù)和”，因為負數(shù)加上下一個元素 “連續(xù)和”只會越來越小；全局最優(yōu)：選取最大“連續(xù)和”

不斷調整最大子序和區(qū)間的起始位置，只要連續(xù)和還是正數(shù)就會對后面的元素起到增大總和的作用。 所以只要連續(xù)和為正數(shù)就保留。

代碼

class Solution {
public:int maxSubArray(vector<int>& nums) {int count=0;//記錄連續(xù)和int result = INT_MIN;//記錄最大連續(xù)和for(int i=0;i<nums.size();i++){count += nums[i];if(count>result) result = count;if(count<0) count = 0;//連續(xù)和為負數(shù)，重新計算連續(xù)和}return result;}
};

• 時間復雜度：O(n)
• 空間復雜度：O(1)

動態(tài)規(guī)劃

動規(guī)五部曲

1）dp數(shù)組及下標i的含義

dp[i]:以nums[i]結尾(包括nums[i])的最大連續(xù)子序列的和

2）遞推公式

dp[i]可以從兩個方向推導出來

1）延續(xù)前面的和：dp[i]=dp[i-1]+nums[i]

2）從nums[i]重新計算：dp[i]=nums[i]

dp[i]=max(dp[i-1]+nums[i],nums[i])

3）dp數(shù)組初始化

根據(jù)遞推公式，dp[i]依賴于dp[i-1]? ?源頭是dp[0]，根據(jù)dp數(shù)組定義，dp[0]=nums[0]

非0下標的dp數(shù)組，可以初始化為任意值，因為可以在后續(xù)計算中被覆蓋，但是為了初始化方便，統(tǒng)一初始為nums[0]

4）遍歷順序

根據(jù)遞推公式，dp[i]依賴于dp[i-1]，從前往后遍歷

for(i=1;i<nums.size();i++)? 注意i從1開始遍歷

5）打印dp數(shù)組

根據(jù)dp數(shù)組定義，最終結果不一定是dp[nums[i]-1]，應該找每一個i為終點的連續(xù)最大子序列，需要把所有結果遍歷一遍，求得最大值

代碼

class Solution {
public:int maxSubArray(vector<int>& nums) {//定義并初始化dp數(shù)組vector<int> dp(nums.size(),nums[0]);int result = INT_MIN;for(int i=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);cout<<dp[i]<<endl;result = max(result,dp[i]);}return result;}
};

上述代碼會出現(xiàn)如下的案例錯誤

錯誤的原因在于：result初始化為最小值，而for循環(huán)中計算的是dp[1]，就是max(dp[0]+nums[1],nums[1])，是從數(shù)組中的第二個元素開始考慮的，如果這樣的話，對于只有一個元素的數(shù)組根本就沒有經(jīng)過for循環(huán)，直接輸出了result，所有result不能這樣初始化，應該初始化為nums[0]，即初始化為數(shù)組的第1個元素值，這樣才能在數(shù)組只有1個元素的情況下，result考慮到第一個元素。

代碼改正如下：

class Solution {
public:int maxSubArray(vector<int>& nums) {//定義并初始化dp數(shù)組vector<int> dp(nums.size(),nums[0]);int result = nums[0];for(int i=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);cout<<dp[i]<<endl;result = max(result,dp[i]);}return result;}
};

• 時間復雜度：O(n)
• 空間復雜度：O(n)