每日OJ题_两个数组dp①_力扣1143. 最长公共子序列
目录
力扣1143. 最长公共子序列
解析代码
力扣1143. 最长公共子序列
1143. 最长公共子序列
难度 中等
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {}
};解析代码
状态表示：
对于两个数组的动态规划，定义状态表是的经验就是：选取第一个数组 [0, i] 区间以及第二个数组 [0, j] 区间作为研究对象。结合题目要求，定义状态表示。
在这道题中，根据题目定义状态表示为：
dp[i][j] 表示： s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的子序列中，最长公共子序列的长度
状态转移方程：
分析状态转移方程的经验就是根据最后一个位置的状况，分情况讨论。 对于 dp[i][j] ，可以根据 s1[i] 与 s2[j] 的字符分情况讨论：
- 两个字符相同， s1[i] = s2[j] ：那么最长公共子序列就在 s1 的 [0, i - 1] 以 及 s2 的 [0, j - 1] 区间上找到⼀个最长的，然后再加上 s1[i] 即可。因此 dp[i][j] = dp[i - 1][j - 1] + 1 ;
- 两个字符不相同， s1[i] != s2[j] ：那么最长公共子序列一定不会同时以 s1[i] 和 s2[j] 结尾。那么我们找最长公共子序列时，有下面三种策略：
- 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最大长度为 dp[i- 1][j] 。
- 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最大长度为 dp[i ][j - 1] 。
- 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最大长度为dp[i - 1][j - 1] 。
我们要三者的最大值即可。但是我们细细观察会发现，第三种包含在第⼀种和第二种情况里面，但是我们求的是最大值，并不影响最终结果。因此只需求前两种情况下的最大值即可。
综上，状态转移方程为：
- if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
- if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ;
初始化、填表顺序、返回值：
初始化：空串是有研究意义的，因此我们将原始 dp 表的规模多加上一行和一列，表示空串。 引入空串后，大大的方便我们的初始化。 但也要注意下标的映射关系，以及里面的值要保证后续填表是正确的。 当 s1 为空时，没有长度，同理 s2 也是。因此第一行和第一列里面的值初始化为 0 即可保证后续填表是正确的，还可以通过在s1和s2最前面加上一个字符来对应下标的映射。
填表顺序：从上往下填写每一行，每一行从左往右，最后返回dp[m][n]。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// dp[i][j] 表示： s1 的 [0, i] 区间以及 s2 的 [0, j] 区间// 内的所有的子序列中，最长公共子序列的长度int m = text1.size(), n = text2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// text1 = " " + text1, text2 = " " + text2; // 注释掉，在原数组找i，j就要-1for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){if(text1[i - 1] == text2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}return dp[m][n];}
};