1143.最長公共子序列

題目要求：給定兩個字符串?text1 和?text2，返回這兩個字符串的最長公共子序列的長度。

一個字符串的?子序列?是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。

若這兩個字符串沒有公共子序列，則返回 0。

示例 1:

• 輸入：text1 = "abcde", text2 = "ace"
• 輸出：3
• 解釋：最長公共子序列是 "ace"，它的長度為 3。

思路

這里不要求子序列是連續(xù)的。

dp[i][j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j]。這樣能夠簡化數(shù)組在第一行和第一列的初始化邏輯。

主要就是兩大情況： text1[i - 1] 與 text2[j - 1]相同，text1[i - 1] 與 text2[j - 1]不相同

如果text1[i - 1] 與 text2[j - 1]相同，那么找到了一個公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 與 text2[j - 1]不相同，那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

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]);
}

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {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()];}
};

1035.不相交的線

題目要求：我們在兩條獨立的水平線上按給定的順序?qū)懴?A?和?B?中的整數(shù)。

現(xiàn)在，我們可以繪制一些連接兩個數(shù)字?A[i]?和?B[j]?的直線，只要?A[i] == B[j]，且我們繪制的直線不與任何其他連線（非水平線）相交。

以這種方法繪制線條，并返回我們可以繪制的最大連線數(shù)。

思路

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

這么分析完之后，大家可以發(fā)現(xiàn)：本題說是求繪制的最大連線數(shù)，其實就是求兩個字符串的最長公共子序列的長度！所以直接copy代碼就可以了。

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

53. 最大子序和

題目要求：給定一個整數(shù)數(shù)組 nums?，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

• 輸入: [-2,1,-3,4,-1,2,1,-5,4]
• 輸出: 6
• 解釋:?連續(xù)子數(shù)組?[4,-1,2,1] 的和最大，為?6。

思路

dp[i]：包括下標i（以nums[i]為結(jié)尾）的最大連續(xù)子序列和為dp[i]。

dp[i]只有兩個方向可以推出來：

• dp[i - 1] + nums[i]，即：nums[i]加入當前連續(xù)子序列和
• nums[i]，即：從頭開始計算當前連續(xù)子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

根據(jù)dp[i]的定義，很明顯dp[0]應(yīng)為nums[0]即dp[0] = nums[0]。

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

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