dpi定义为s1[0..i-1]与s2[0..j-1]的lcs长度，因可自然处理空串边界（i=0或j=0时值为0），避免负下标越界；初始化用vector(m+1,vector(n+1,0))，状态转移分字符相等（dpi-1+1）与不等（max(dpi-1,dpi)）两种情况。
为什么 dp[i][j] 要定义为 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
因为下标从 0 开始时，空字符串对应长度为 0，i=0 或 j=0 就能自然表示“其中一个串为空”，边界初始化直接设为 0。如果定义成 s1[0..i]，就得额外处理负下标或偏移，容易在循环里越界或漏初始化。
常见错误现象：dp[i][j] = dp[i-1][j-1] + 1 时没判 i > 0 && j > 0，导致访问 dp[-1][-1]（实际是内存越界）；或者初始化时只填了 dp[0][*] 却忘了 dp[*][0]，结果所有以 s2 首字符开头的匹配都出错。
- 初始化二维数组：用
vector<vector>> dp(m+1, vector<int>(n+1, 0))</int></vector>，其中m = s1.size(),n = s2.size() - 状态转移必须分两种情况：
s1[i-1] == s2[j-1]时取dp[i-1][j-1] + 1；否则取max(dp[i-1][j], dp[i][j-1]) - 不要在循环里写
dp[i][j] = max(dp[i-1][j-1] + (s1[i]==s2[j] ? 1 : 0), ...)—— 这混淆了“是否相等”和“是否能继承对角线”的逻辑，会漏掉不相等时的横向/纵向最大值
如何还原 LCS 字符串而不是只返回长度
只存长度的 dp 表无法回溯路径，必须边填表边记录决策，或填完后反向扫描。推荐后者：从 dp[m][n] 出发，往左上回退，遇到相等字符就加入结果，注意不是所有 dp[i-1][j-1] + 1 == dp[i][j] 都说明字符匹配——只有当 s1[i-1] == s2[j-1] 且该等式成立时才算。
常见错误现象：回溯时无条件执行 i--, j--，导致跳过本应向左或向上走的分支；或把结果字符串顺序搞反（没 reverse），输出的是逆序 LCS。
立即学习“C++免费学习笔记（深入）”；
- 回溯循环条件是
i > 0 && j > 0，不是i >= 0 && j >= 0 - 判断匹配：仅当
s1[i-1] == s2[j-1]时，把s1[i-1]推入临时字符串，并执行i--, j-- - 否则，比较
dp[i-1][j]和dp[i][j-1]：哪个大就往哪走；相等时任意选一个（不影响长度，但影响具体子序列，题目没要求唯一解就可任选）
string 传参用 const 引用，但 dp 数组别用 vector<string></string>
求长度时，dp 存 int 足够；若误用 vector<vector>></vector> 存每个位置的 LCS 字符串，时间与空间直接爆炸——每次状态转移都要字符串拼接（O(len)），最坏总复杂度 O(mn×min(m,n))，远超标准 O(mn)。
使用场景：只要求长度，绝对不要建 string 二维表；需要输出方案时，先用 int 表算出长度，再单独一次 O(m+n) 回溯构造字符串。
- 性能影响：对两个长度 1000 的字符串，
int表约 4MB 内存，string表可能超 500MB 且超时 - 兼容性：C++11 起
std::string移动语义缓解部分问题，但无法改变算法复杂度本质 - 参数写法示例：
int lcs(const string& s1, const string& s2)—— 避免拷贝，又不会意外修改原串
边界测试容易漏掉空串或单字符
空串是合法输入，s1 = "" 时答案必须是 0；单字符情形（如 s1="a", s2="b"）会暴露状态转移是否漏判相等情况。很多实现能过样例但挂在这类 case 上。
错误信息示例：runtime error: index -1 out of bounds for type 'int [1001][1001]'，往往是因为没把 i 和 j 的有效范围控制在 [1, m] 和 [1, n]，却用 i-1 当数组下标去访问固定大小数组。
- 务必测：
lcs("", "abc") → 0、lcs("x", "x") → 1、lcs("ab", "ba") → 1（不是 2） - 如果用静态数组如
int dp[1005][1005]，循环变量要从 1 开始，且确保输入长度 ≤ 1000 - 用
vector更安全，但别写成dp[i][j] = dp[i-1][j-1] + (s1[i]==s2[j])—— 这里i是从 0 开始的下标，而dp定义是基于长度的，下标错位必崩
