1 今日打卡
最长公共子序列 1143. 最长公共子序列 – 力扣（LeetCode）
不相交的线 1035. 不相交的线 – 力扣（LeetCode）
最大子数组和 53. 最大子数组和 – 力扣（LeetCode）
判断子序列 392. 判断子序列 – 力扣（LeetCode）
2 dp五部曲
dp数组及其下标的含义
状态转移方程
初始化
遍历顺序
手动模拟
3 最长公共子序列
3.1 思路
第一步：
定义 dp[i][j]：表示 text1 的前 i 个字符（text1[0..i-1]）和 text2 的前 j 个字符（text2[0..j-1]）的最长公共子序列的长度。 采用 i-1/j-1 对应字符串字符的原因： 让 dp[0][j] 和 dp[i][0] 都为 0（空字符串与任意字符串的公共子序列长度为 0），无需额外处理边界，简化初始化逻辑。
第二步：
情况 1：text1[i-1] == text2[j-1]（当前字符匹配） 说明该字符可以加入公共子序列，因此 dp[i][j] = dp[i-1][j-1] + 1（前 i-1 和 j-1 个字符的 LCS 长度 + 1）。 情况 2：text1[i-1] != text2[j-1]（当前字符不匹配） 此时需要舍弃其中一个字符，取两种情况的最大值： 舍弃 text1[i-1]：取 dp[i-1][j]（text1 前 i-1 个字符和 text2 前 j 个字符的 LCS）； 舍弃 text2[j-1]：取 dp[i][j-1]（text1 前 i 个字符和 text2 前 j-1 个字符的 LCS）； 因此 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])。
第三步：
dp 是 (len1+1) × (len2+1) 的二维数组，所有元素默认初始化为 0； dp[0][j] = 0：text1 取前 0 个字符（空字符串），和 text2 前 j 个字符无公共子序列； dp[i][0] = 0：text2 取前 0 个字符（空字符串），和 text1 前 i 个字符无公共子序列； 初始化后，后续只需按状态转移方程更新即可。
第四步：
dp[i][j] 依赖于 dp[i-1][j-1]（左上角）、dp[i-1][j]（正上方）、dp[i][j-1]（正左方），因此必须按从上到下、从左到右的顺序遍历： 外层循环：i 从 1 到 len1（遍历 text1 的每个字符）； 内层循环：j 从 1 到 len2（遍历 text2 的每个字符）。 最终结果存储在 dp[len1][len2]（整个 text1 和 text2 的 LCS 长度），无需额外维护最大值变量。
第五步：
以 text1 = "abcde"、text2 = "ace" 为例： 初始化：dp 数组全为 0； i=1（text1 [0]='a'）： j=1（text2 [0]='a'）→ 匹配 → dp [1][1] = dp [0][0]+1=1； j=2（text2 [1]='c'）→ 不匹配 → dp [1][2] = max (dp [0][2], dp [1][1])=1； j=3（text2 [2]='e'）→ 不匹配 → dp [1][3] = max (dp [0][3], dp [1][2])=1； i=2（text1 [1]='b'）： j=1→不匹配→dp [2][1]=max (dp [1][1], dp [2][0])=1； j=2→不匹配→dp [2][2]=max (dp [1][2], dp [2][1])=1； j=3→不匹配→dp [2][3]=max (dp [1][3], dp [2][2])=1； i=3（text1 [2]='c'）： j=2（text2 [1]='c'）→ 匹配 → dp [3][2] = dp [2][1]+1=2； i=5（text1 [4]='e'）： j=3（text2 [2]='e'）→ 匹配 → dp [5][3] = dp [4][2]+1=3； 最终 dp[5][3] = 3，对应 LCS 为 "ace"，长度 3。
3.2 实现代码
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 获取两个字符串的长度
int len1 = text1.length(), len2 = text2.length();
// 1. 定义dp数组：dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度
// 维度为(len1+1)x(len2+1)，默认初始值为0，无需额外初始化
int[][] dp = new int[len1 + 1][len2 + 1];
// 2. 遍历顺序：从上到下、从左到右
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 3. 状态转移方程：当前字符匹配
if (text1.charAt(i – 1) == text2.charAt(j – 1)) {
// 匹配时，LCS长度 = 前i-1/j-1个字符的LCS长度 + 1
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
// 不匹配时，取“舍弃text1[i-1]”或“舍弃text2[j-1]”的最大值
dp[i][j] = Math.max(dp[i][j – 1], dp[i – 1][j]);
}
}
}
// 4. 返回整个text1和text2的最长公共子序列长度
return dp[len1][len2];
}
}
4 不相交的线
4.1 思路
这道题看懂题目，其实跟前面一题：最长公共子序列一模一样。这里就只贴代码
4.2 实现代码
class Solution {
// 题目：不相交的线 – 本质是求两个数组的最长公共子序列（LCS）长度
public int maxUncrossedLines(int[] nums1, int[] nums2) {
// 获取两个数组的长度
int len1 = nums1.length, len2 = nums2.length;
// 定义dp数组：dp[i][j]表示nums1前i个元素和nums2前j个元素能画出的不相交线的最大数量
// 等价于nums1[0..i-1]和nums2[0..j-1]的最长公共子序列长度
int[][] dp = new int[len1 + 1][len2 + 1];
// 遍历顺序：从上到下、从左到右（依赖左上/上/左的结果）
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 情况1：当前元素匹配（nums1[i-1] == nums2[j-1]）
// 可以画一条线，数量 = 前i-1/j-1个元素的最大数量 + 1
if (nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
// 情况2：当前元素不匹配
// 取“舍弃nums1[i-1]”或“舍弃nums2[j-1]”的最大值（不相交的线数量不变）
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
// 最终结果：整个nums1和nums2能画出的不相交线的最大数量
return dp[len1][len2];
}
}
5 最大子数组和
5.1 思路
第一步：
定义 dp[i]：以数组中第 i 个元素（nums[i]）结尾的连续子数组的最大和。 为什么聚焦 “以 nums [i] 结尾”？ 因为子数组是连续的，要计算包含 nums[i] 的最大子数组和，只能从 “包含 nums [i-1] 的最大子数组和 + nums [i]” 或 “仅 nums [i] 本身” 中选择，这个定义能让状态转移逻辑唯一且清晰。
第二步：
核心逻辑：对于 nums[i]，有两种选择 —— 选择 1：将 nums[i] 加入以 nums[i-1] 结尾的子数组，此时和为 dp[i-1] + nums[i]； 选择 2：以 nums[i] 为起点重新开始一个子数组，此时和为 nums[i]；
取两者的最大值作为 dp[i]，即： plaintext dp[i] = Math.max(dp[i-1] + nums[i], nums[i]) 这个方程的本质是：如果延续前序子数组的和比重新开始更优，就延续；否则重新开始。
第三步：
dp[0] = nums[0]：以第一个元素结尾的子数组只有它自己，最大和就是它本身； 结果变量 res = dp[0]：初始时最大和就是第一个元素的和，后续遍历中不断更新。
第四步：
因为 dp[i] 依赖于 dp[i-1]（前一个位置的结果），所以必须从左到右遍历数组（i 从 1 到 len-1）； 每计算出一个 dp[i]，就和当前的 res 比较，将 res 更新为更大的值（res 记录全局最大子数组和）。
第五步：
以经典示例 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例： 初始化：dp[0] = -2，res = -2； i=1（nums[1]=1）：dp[1] = max(-2+1, 1) = max(-1,1)=1 → res=1； i=2（nums[2]=-3）：dp[2] = max(1-3, -3) = max(-2,-3)=-2 → res 仍为 1； i=3（nums[3]=4）：dp[3] = max(-2+4,4) = max(2,4)=4 → res=4； i=4（nums[4]=-1）：dp[4] = max(4-1,-1)=3 → res 仍为 4； i=5（nums[5]=2）：dp[5] = max(3+2,2)=5 → res=5； i=6（nums[6]=1）：dp[6] = max(5+1,1)=6 → res=6； i=7（nums[7]=-5）：dp[7] = max(6-5,-5)=1 → res 仍为 6； i=8（nums[8]=4）：dp[8] = max(1+4,4)=5 → res 仍为 6； 最终返回 res=6，对应最大子数组 [4,-1,2,1]。
5.2 实现代码
class Solution {
public int maxSubArray(int[] nums) {
// 获取数组长度
int len = nums.length;
// 处理边界情况：空数组返回0（题目中nums非空，可省略，但增加鲁棒性）
if (len == 0) {
return 0;
}
// 1. 定义dp数组：dp[i]表示以nums[i]结尾的连续子数组的最大和
int[] dp = new int[len];
// 2. 初始化：第一个元素结尾的子数组和就是它本身
dp[0] = nums[0];
// 初始化全局最大和，初始值为第一个元素的和
int res = dp[0];
// 3. 遍历顺序：从左到右遍历（i从1开始）
for (int i = 1; i < len; i++) {
// 4. 状态转移方程：
// 选择1：延续前序子数组（dp[i-1]+nums[i]）；选择2：重新开始子数组（nums[i]）
// 取两者的最大值作为dp[i]
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
// 5. 更新全局最大和：如果当前dp[i]更大，就更新res
if (dp[i] > res) {
res = dp[i];
}
}
// 返回全局最大子数组和
return res;
}
}
6 判断子序列
6.1 思路
第一步：
定义 dp[i][j]：表示字符串 s 的前 i 个字符（s[0..i-1]）和字符串 t 的前 j 个字符（t[0..j-1]）的最长公共子序列的长度（且这个子序列就是s的前缀）。 采用 i-1/j-1 对应字符的原因：让 dp[0][j] = 0（空字符串与任意t的前缀公共子序列长度为 0）、dp[i][0] = 0（任意s的前缀与空字符串无公共子序列），简化边界处理
第二步：
子序列的核心是：s 的字符必须按顺序出现在 t 中，且不需要连续。状态转移需贴合这一特性： 情况 1：s[i-1] == t[j-1]（当前字符匹配） 说明s的第i个字符在t的第j个字符处匹配成功，公共子序列长度 = 前i-1和j-1个字符的长度 + 1 → dp[i][j] = dp[i-1][j-1] + 1。 情况 2：s[i-1] != t[j-1]（当前字符不匹配） 此时只能舍弃t的第j个字符，继续用t的前j-1个字符匹配s的前i个字符 → dp[i][j] = dp[i][j-1]（注意：这里和普通 LCS 的区别是只舍弃 t 的字符，因为我们只关心s是否能按顺序出现在t中，不能舍弃s的字符）。
第三步：
dp 是 (length1+1) × (length2+1) 的二维数组，所有元素默认初始化为 0； dp[0][j] = 0：空字符串s是任何t的子序列，公共子序列长度为 0； dp[i][0] = 0：非空s无法匹配空字符串t，公共子序列长度为 0； 初始化后无需额外赋值，直接按状态转移方程遍历即可。
第四步：
dp[i][j] 依赖于 dp[i-1][j-1]（左上角）和 dp[i][j-1]（正左方），因此必须按从上到下、从左到右遍历： 外层循环：i 从 1 到 length1（遍历s的每个字符）； 内层循环：j 从 1 到 length2（遍历t的每个字符）。
第五步：
以 s = "abc"、t = "ahbgdc" 为例： 初始化：dp 数组全为 0； i=1（s [0]='a'）： j=1（t [0]='a'）→ 匹配 → dp [1][1] = dp [0][0]+1=1； j=2~6 → 不匹配 → dp [1][j] = dp [1][j-1]=1； i=2（s [1]='b'）： j=1→不匹配→dp [2][1]=dp [2][0]=0； j=2→不匹配→dp [2][2]=dp [2][1]=0； j=3（t [2]='b'）→ 匹配 → dp [2][3] = dp [1][2]+1=2； j=4~6→不匹配→dp [2][j]=dp [2][j-1]=2； i=3（s [2]='c'）： j=1~5→不匹配→dp [3][j]=dp [3][j-1]=2； j=6（t [5]='c'）→ 匹配 → dp [3][6] = dp [2][5]+1=3； 最终 dp[3][6] = 3，等于s的长度 3 → 返回true（abc是ahbgdc的子序列）。
6.2 实现代码
class Solution {
public boolean isSubsequence(String s, String t) {
// 获取s和t的长度
int length1 = s.length(), length2 = t.length();
// 1. 定义dp数组：dp[i][j]表示s前i个字符和t前j个字符的最长公共子序列长度
// （该子序列是s的前缀，用于判断s是否能按顺序出现在t中）
int[][] dp = new int[length1 + 1][length2 + 1];
// 2. 遍历顺序：从上到下、从左到右
for (int i = 1; i <= length1; i++) {
for (int j = 1; j <= length2; j++) {
// 3. 状态转移方程：当前字符匹配
if (s.charAt(i – 1) == t.charAt(j – 1)) {
// 匹配成功，公共子序列长度+1
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
// 当前字符不匹配，舍弃t的第j个字符，继承左方的结果
dp[i][j] = dp[i][j – 1];
}
}
}
// 4. 核心判断：若最长公共子序列长度等于s的长度，说明s是t的子序列
return dp[length1][length2] == length1;
}
}
