17370845950

二维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)) 可行吗？要注意什么

可以滚动数组优化，但仅适用于求长度，不适用于还原字符串。因为还原需要整张表的路径信息。

• 只保留两行：prev[j] 和 curr[j]，每次迭代后交换
• 注意内层循环必须从左到右，因为 curr[j] 依赖 curr[j-1]（左）和 prev[j-1]（左上）
• 若用一维数组（dp[j]），需临时存 dp[j-1] 前的值，否则被覆盖；常见错误是没保存 prev[j-1] 就覆盖了
• 字符串长度差异大时，先让短字符串做列方向，能省更多空间

实际写的时候，别急着优化空间——先跑通二维版本，确认字符索引和边界处理都对，再考虑滚动数组。LCS 的坑几乎全在下标偏移和边界初始化上，而不是算法本身。