《LeetCode 646 最长数对链 || LeetCode 1143 最长公共子序列》

一、题目二、做题思路2.1 状态表示核心基础定义dp[i]表示以第i个数对结尾的最长数对链的长度。由于数对可任意顺序选择我们先按left升序排序使得后续只需考虑j i的前驱具备无后效性。2.2 状态转移方程关键难点枚举前驱j i若pairs[i][0] pairs[j][1]则可以将数对i接在数对j后面形成更长的链长度为dp[j] 1。取所有合法j中的最大值dp[i] max(dp[i], dp[j] 1)满足pairs[i][0] pairs[j][1]。2.3 初始化边界防护每个数对自身可构成长度为 1 的链因此dp[i] 1对所有i。2.4 填表顺序递推方向dp[i]依赖所有j i的状态因此从左到右遍历i内层遍历所有j i确保前置状态已就绪。2.5 返回值目标映射取所有dp[i]中的最大值返回该最大值。三、代码class Solution { public: int wiggleMaxLength(vectorint nums) { int n nums.size(); // 边界处理空数组无摆动序列 if (n 0) return 0; // 1. 创建dp表 // f[i] : 以 nums[i] 结尾且最后一段比较关系为“上升”nums[i-1] nums[i]的摆动序列的最大长度 // g[i] : 以 nums[i] 结尾且最后一段比较关系为“下降”nums[i-1] nums[i]的摆动序列的最大长度 // 初始化每个元素自身可构成长度为 1 的摆动序列既可以是上升也可以是下降的起点 vectorint f(n, 1); vectorint g(n, 1); // 2. 填表顺序从左到右i 从 1 到 n-1因为 f[i]/g[i] 依赖所有 j i 的状态 for (int i 1; i n; i) { for (int j 0; j i; j) { // 3. 状态转移方程 // 若 nums[i] nums[j]则可以将 nums[i] 接在“下降”结尾的序列后面g[j]形成上升结尾的序列 // 长度 g[j] 1同时保留 f[i] 原有的值可能通过其他 j 得到更长的长度 if (nums[i] nums[j]) { f[i] max(f[i], g[j] 1); } // 若 nums[i] nums[j]则可以将 nums[i] 接在“上升”结尾的序列后面f[j]形成下降结尾的序列 // 长度 f[j] 1同时保留 g[i] 原有的值 else if (nums[i] nums[j]) { g[i] max(g[i], f[j] 1); } // 若相等无法构成摆动跳过状态保持不变 } } // 4. 返回值所有 f[i] 和 g[i] 中的最大值 int ret 1; for (int i 0; i n; i) { ret max(ret, max(f[i], g[i])); } return ret; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求返回两个字符串的最长公共子序列的长度。定义dp[i][j]表示text1的前i个字符与text2的前j个字符的最长公共子序列长度。6.2 状态转移方程关键难点对于text1[i]和text2[j]从1开始计数若text1[i] text2[j]则当前字符可纳入公共子序列长度 dp[i-1][j-1] 1。否则取不包含text1[i]或不包含text2[j]的较大者即dp[i][j] max(dp[i-1][j], dp[i][j-1])。6.3 初始化边界防护dp[0][j] dp[i][0] 0表示空串与任意串的公共子序列长度为 0默认初始化为 0 即可。6.4 填表顺序递推方向dp[i][j]依赖左上dp[i-1][j-1]、上方dp[i-1][j]和左方dp[i][j-1]因此从上到下、从左到右遍历i和j确保前置状态已就绪。6.5 返回值目标映射最终返回dp[n1][n2]即为两个完整字符串的最长公共子序列长度。七、代码class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 text1.size(); int n2 text2.size(); // 1. 创建dp表多开一行一列方便处理边界 // dp[i][j] 表示 text1 的前 i 个字符text1[0..i-1]和 text2 的前 j 个字符text2[0..j-1]的最长公共子序列长度 vectorvectorint dp(n1 1, vectorint(n2 1, 0)); // 为了便于下标对齐在字符串前面添加一个占位符空格 // 这样 text1[i] 对应原 text1 的第 i-1 个字符i 从 1 开始 text1 text1; text2 text2; // 2. 初始化dp[0][j] 0 和 dp[i][0] 0默认已初始化为 0 // 3. 填表顺序从上到下i 从 1 到 n1从左到右j 从 1 到 n2 // 因为 dp[i][j] 依赖于 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]均在左上方、上方或左方 // 按行优先遍历即可保证依赖状态已计算。 for (int i 1; i n1; i) { for (int j 1; j n2; j) { // 4. 状态转移方程 // 若当前两个字符相等则当前 LCS 长度 左上角 dp[i-1][j-1] 1 if (text1[i] text2[j]) { dp[i][j] dp[i - 1][j - 1] 1; } else { // 若不等则取上方或左方中的较大值即去掉 text1[i] 或 text2[j] 后的 LCS dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } // 5. 返回值dp[n1][n2] 即为两个字符串的最长公共子序列长度 return dp[n1][n2]; } };八、流程图