二维DP数组开dpm+1是为了自然容纳空字符串边界，使dp0和dp*初始化为0，避免下标越界与逻辑错误，实际匹配从i=1,j=1开始，答案在dpm。
为什么二维DP数组要开 dp[m+1][n+1] 而不是 dp[m][n]
因为状态转移依赖「空字符串」作为边界：当 i=0（s1 为空）或 j=0（s2 为空）时，LCS 长度必为 0。开 m+1 行 n+1 列可自然容纳这些边界，避免每次判断 i==0 || j==0。否则容易在循环里写错下标，比如把 dp[i-1][j-1] 写成 dp[i][j] 导致越界或逻辑错误。
- 初始化全部为 0，
dp[0][*]和dp[*][0]自动满足边界条件 - 实际匹配从
i=1, j=1开始，对应s1[0]和s2[0] - 最终答案在
dp[m][n]，不是dp[m-1][n-1]
dp[i][j] 的状态转移怎么写才不漏情况
核心就两种情况，必须覆盖所有分支：
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
- 相等时，一定取左上角 +1；不能写成
max(...)，否则可能丢掉这个唯一最优路径 - 不等时，必须取「上方」和「左方」的最大值；只取一个会漏解（比如上方是 2、左方是 3，漏掉左方就错了）
- 注意字符索引是
i-1和j-1，因为dp下标比字符串下标大 1
如何从 dp 数组还原出具体的 LCS 字符串
反向遍历 dp 数组，从 dp[m][n] 往回走，靠比较值的变化来决定路径：
string lcs = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1[i-1] == s2[j-1]) {
lcs += s1[i-1];
i--; j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
reverse(lcs.begin(), lcs.end());
- 只有当字符相等且
dp值确实来自左上角（即dp[i][j] == dp[i-1][j-1] + 1）才加入结果 -
dp[i-1][j] > dp[i][j-1]表示当前值继承自上方，说明s1[i-1]没被选中 - 如果两者相等（
==），任选其一即可，但代码里用了>=的等效写法（else 分支兜底），这是常见且安全的写法
空间优化到 O(min(m,n)) 可行吗？要注意什么
可以滚动数组优化，但仅适用于求长度，不适用于还原字符串。因为还原需要整张表的路径信息。
立即学习“C++免费学习笔记（深入）”；
- 只保留两行：
prev[j]和curr[j]，每次迭代后交换 - 注意内层循环必须从左到右，因为
curr[j]依赖curr[j-1]（左）和prev[j-1]（左上） - 若用一维数组（
dp[j]），需临时存dp[j-1]前的值，否则被覆盖；常见错误是没保存prev[j-1]就覆盖了 - 字符串长度差异大时，先让短字符串做列方向，能省更多空间
