leedcode-算法刷题第三十六天-
目录
leedcode 算法刷题第三十六天
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()];
}
};1. 问题理解
目标：找到两个字符串 text1 和 text2 的最长公共子序列的长度。
子序列：不同于子串，子序列不要求字符是连续的，但必须保持原有的相对顺序。
例如：text1 = "abcde", text2 = "ace"
它们的公共子序列有 “a”, “c”, “e”, “ac”, “ae”, “ce”, “ace”。
其中最长的就是 “ace”，长度为 3。函数应该返回 3。
2. 动态规划思路
核心思想是使用一个二维数组 dp 来存储子问题的解，从而避免重复计算。
dp[i][j]的定义：表示text1的前i个字符 和text2的前j个字符 的最长公共子序列的长度。- 注意：这里的
i和j是长度，而不是索引。text1[i-1]才是第i个字符。
- 注意：这里的
3. 状态转移方程
如何推导出 dp[i][j]？这取决于 text1 和 text2 的最后一个字符是否相等。
如果
text1[i - 1] == text2[j - 1]：- 这个相同的字符肯定属于公共子序列的一部分。
- 那么，
text1的前i个字符和text2的前j个字符的 LCS 长度，就等于text1的前i-1个字符和text2的前j-1个字符的 LCS 长度 再加 1。 - 公式：
dp[i][j] = dp[i - 1][j - 1] + 1
如果
text1[i - 1] != text2[j - 1]：最后一个字符不同，它们不可能同时出现在当前的公共子序列中。
那么，
dp[i][j]的值只能继承自它之前已经解决的两个子问题中的最大值：- Case 1：忽略
text1的最后一个字符，看text1[0..i-2]和text2[0..j-1]的 LCS 长度，即dp[i-1][j]。 - Case 2：忽略
text2的最后一个字符，看text1[0..i-1]和text2[0..j-2]的 LCS 长度，即dp[i][j-1]。
- Case 1：忽略
公式：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
4. 代码逐行解析
cpp
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
// 1. 初始化DP表 (dp table)
// 创建一个大小为 (len(text1)+1) x (len(text2)+1) 的二维向量，所有值初始化为0。
// 多出来的一行一列是为了方便处理空字符串的情况（即边界条件）。
// 例如，dp[0][j] 表示 text1取前0个字符（空串）和text2的前j个字符的LCS，长度自然为0。
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
// 2. 填充DP表
// i 从1遍历到 text1的长度，代表逐步考虑text1中更多的字符。
for (int i = 1; i <= text1.size(); i++) {
// j 从1遍历到 text2的长度，代表逐步考虑text2中更多的字符。
for (int j = 1; j <= text2.size(); j++) {
// 检查当前字符是否相等（注意索引要减1）
if (text1[i - 1] == text2[j - 1]) {
// 字符相等，应用状态转移方程1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 字符不相等，应用状态转移方程2
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 3. 返回结果
// dp[text1.size()][text2.size()] 包含了整个问题的解：text1和text2完整的LCS长度。
return dp[text1.size()][text2.size()];
}
};5. 举例说明
以 text1 = "abcde", text2 = "ace" 为例，DP 表的填充过程如下（为节省空间，只展示关键步骤）：
| dp | '' | ‘a’ | ‘c’ | ’e’ |
|---|---|---|---|---|
| ’’ | 0 | 0 | 0 | 0 |
| ‘a’ | 0 | 1 | 1 | 1 |
| ‘b’ | 0 | 1 | 1 | 1 |
| ‘c’ | 0 | 1 | 2 | 2 |
| ‘d’ | 0 | 1 | 2 | 2 |
| ’e’ | 0 | 1 | 2 | 3 |
i=1, j=1: 比较 ‘a‘ 和 ‘a‘，相等。dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1。i=1, j=2: 比较 ‘a‘ 和 ‘c‘，不等。dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1。i=1, j=3: 比较 ‘a‘ 和 ‘e‘，不等。dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1。i=2, j=1: 比较 ‘b‘ 和 ‘a‘，不等。dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1。i=3, j=2: 比较 ‘c‘ 和 ‘c‘，相等。dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2。i=5, j=3: 比较 ‘e‘ 和 ‘e‘，相等。dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3。这就是最终答案。
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()];
}
};跟上个题代码一样。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size());
if (nums.empty())
return 0;
dp[0] = nums[0];
int value = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i],nums[i]);
value = max(value,dp[i]);
}
return value;}
};状态定义：dp[i] 表示以 nums[i] 结尾的最大子数组和
状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])- 要么从当前元素重新开始一个子数组
- 要么将当前元素加入到前面的子数组中