最长公共子序列
最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili
本题和上一题718.最长重复子数组在很多方面相似，区别在与不需要连续，因此在dp数组的推导上有些改变。
由于不需要连续，dp[i][j]的值针对text1和text2相同及不同这两种情况有不同的表示。
首先 dp[i][j]表示序列text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度
当text[i-1] == text[j-1]时，dp[i][j] = dp[i-1][j-1]+1，而当text1[i-1]!=text2[j-1]时，dp[i][j] = max(dp[i-1][j],dp[i][j-1])，dp[i][j]由数组左和上的较大值确定。
由此，dp[i][j]由左上部分确认，当i j为0时，表示的序列为空，空序列与任何序列的最长公共子序列均为空，长度为0，dp[0][0]、dp[0][1]、dp[1][0]都为0。
i，j两个变量循环遍历。
最后返回dp[text1.size()][text2.size()]。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
// 创建一个二维向量 dp，用于存储动态规划的状态值
// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度
// 初始化 dp 的大小为 (text1.size()+1) x (text2.size()+1)，值全部为 0
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
// 双层循环遍历 text1 和 text2
for (int i = 1; i <= text1.size(); i++) { // i 从 1 开始，直到 text1.size()
for (int j = 1; j <= text2.size(); j++) { // j 从 1 开始，直到 text2.size()
// 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同
if (text1[i - 1] == text2[j - 1]) {
// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值
// 这意味着当前字符不包含在 LCS 中
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 返回 dp[text1.size()][text2.size()]，即 text1 和 text2 的 LCS 长度
return dp[text1.size()][text2.size()];
}算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)，m和n分别代表两个序列的长度，二维数组，二维循环遍历。
不相交的线
和上题一致，换些变量便能解决，不过真要面试的时候，希望能想到吧。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
// 创建一个二维向量 dp，用于存储动态规划的状态值
// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的最长公共子序列的长度
// 初始化 dp 的大小为 (nums1.size()+1) x (nums2.size()+1)，值全部为 0
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
// 双层循环遍历 nums1 和 nums2
for (int i = 1; i <= nums1.size(); i++) { // i 从 1 开始，直到 nums1.size()
for (int j = 1; j <= nums2.size(); j++) { // j 从 1 开始，直到 nums2.size()
// 如果 nums1 的第 i 个元素和 nums2 的第 j 个元素相同
if (nums1[i - 1] == nums2[j - 1]) {
// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值
// 这意味着当前元素不包含在 LCS 中
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 返回 dp[nums1.size()][nums2.size()]，即 nums1 和 nums2 的 LCS 长度
// 这也是不相交的直线段的最大数量
return dp[nums1.size()][nums2.size()];
}算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)。
最大子序和
之前用过贪心算法解这道题，当子序和为负，则抛弃当前子序和，从下一个位置开始计算子序和。这里使用动态规划也是类似的。
由于是连续的子序和，dp[i]表示到i为止的最大子序和（此处应包含nums[i]）
dp[i] = max(dp[i-1]+nums[i],nums[i])，这里可以想象贪心的思路，当dp[i-1]为负时，自然dp[i-1]+nums[i]要小于nums[i]。
因此，唯一需要的是当前元素的前一位的dp值，dp[0] = nums[0]。
从前往后遍历
最后返回dp数组中的最大值。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 创建一个向量 dp，用于存储以第 i 个元素结尾的最大子数组和
// 初始化 dp 的大小与 nums 相同，值全部为 0
vector<int> dp(nums.size(), 0);
// dp[0] 是数组第一个元素的值，因为一个元素的子数组和就是它本身
dp[0] = nums[0];
// 遍历数组 nums，从第二个元素开始
for (int i = 1; i < nums.size(); i++) {
// 如果以第 i-1 个元素结尾的最大子数组和小于 0
if (dp[i - 1] < 0) {
// 则以第 i 个元素结尾的最大子数组和就是第 i 个元素的值
// 因为加上前面的子数组和会使得和更小
dp[i] = nums[i];
} else {
// 如果以第 i-1 个元素结尾的最大子数组和大于等于 0
// 则将第 i 个元素的值加到以第 i-1 个元素结尾的最大子数组和上
// 这样可以保持子数组的连续性
dp[i] = dp[i - 1] + nums[i];
}
}
// 使用 STL 中的 max_element 函数找出 dp 中的最大值
// 这个最大值就是整个数组的最大子数组和
return *max_element(dp.begin(), dp.end());
}
};
算法的时间复杂度为O(n),空间复杂度为O(n)。
判断子序列
同样和最长公共子序列相似，在遍历过程中，当dp[i][j] == s.size()时，表示s为t的子序列，否则s不是t的子序列，具体代码如下。
class Solution {
public:
// 定义一个成员函数，用于判断 s 是否为 t 的子序列
bool isSubsequence(string s, string t) {
// 如果 s 为空字符串，那么它是任何字符串的子序列
if (s.size() == 0) {
return true;
}
// 创建一个二维向量 dp，用于存储动态规划的状态值
// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的匹配长度
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
// 双层循环遍历 s 和 t
for (int i = 1; i <= s.size(); i++) { // i 从 1 开始，直到 s.size()
for (int j = 1; j <= t.size(); j++) { // j 从 1 开始，直到 t.size()
// 如果 s 的第 i 个字符和 t 的第 j 个字符相同
if (s[i - 1] == t[j - 1]) {
// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1
dp[i][j] = dp[i - 1][j - 1] + 1;
// 如果匹配长度等于 s 的长度，说明 s 是 t 的子序列
if (dp[i][j] == s.size()) {
return true;
}
} else {
// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值
// 这表示当前字符不包含在子序列中
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 如果遍历完 dp 数组后没有找到匹配长度等于 s 长度的状态，则 s 不是 t 的子序列
return false;
}
};
算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)。