LeetCode-1143：dp[i][j]如何表示的最优匹配？
摘要：本题在线练习：LeetCode 1143. 最长公共子序列 - 在线练习（免费 · 无需登录 · AI 辅助）(https:onefly.topzero2Leetcodeplayg
本题在线练习：LeetCode 1143. 最长公共子序列 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=1143)
配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。
题目概述
给定两个字符串 text1 和 text2，返回它们的最长公共子序列（LCS, Longest Common Subsequence）长度。
子序列强调“相对顺序”，不要求连续。例如 "abcde" 的子序列可以是 "ace"。
核心思路：把问题缩小成“两个前缀”的 LCS
设：
dp[i][j] 表示 text1 的前 i 个字符（text1[:i]）与 text2 的前 j 个字符（text2[:j]）的 LCS 长度。
这样定义的好处是：dp[i][j] 的答案可以由更短的前缀推出来。
转移分两种情况：
如果 text1[i-1] == text2[j-1]，那么这个字符可以作为公共子序列的最后一个字符：
dp[i][j] = dp[i-1][j-1] + 1
如果不相等，那么最后一个字符至少有一个不参与 LCS，只能从“去掉一个末尾字符”的两个选择中取最大：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化：只要有一个前缀长度为 0，则 LCS 为 0，所以第一行第一列都是 0。
代码实现（二维 dp）
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
逐行拆解：为什么要用 (m+1) x (n+1)
把 dp 做成多一行、多一列，是为了让 dp[0][*]、dp[*][0] 代表“空串前缀”，从而避免边界判断。
此时 dp[i][j] 永远对应 text1[:i] 和 text2[:j]，下标 i-1、j-1 刚好指向各自的最后一个字符。
手动模拟：text1="abcde", text2="ace"
当遍历到：
i=1（a）、j=1（a）相等：dp[1][1]=dp[0][0]+1=1
i=3（c）、j=2（c）相等：dp[3][2]=dp[2][1]+1=2
i=5（e）、j=3（e）相等：dp[5][3]=dp[4][2]+1=3
最终答案为 3，对应公共子序列 "ace"。
进阶：一维滚动数组（可选）
二维 dp 直观，但空间是 O(mn)。如果只要长度，可以做空间优化到 O(n)：
用 dp[j] 表示当前行的 dp[i][j]
需要一个变量 prev 保存上一行的 dp[i-1][j-1]
这里不展开写完整代码也能理解：本质是“当前格依赖左、上、左上”，滚动数组要额外记住“左上”。
复杂度分析
时间：O(mn)
空间：二维 O(mn)，滚动后 O(n)
总结
LCS 的关键是把 dp[i][j] 定义成“两个前缀的最优值”。当这个定义建立起来，转移只有两句话：
字符相等：继承左上并 +1
字符不等：在“去掉一个末尾字符”的两条路里取最大
后续很多字符串 DP（编辑距离、最长重复子序列等）都与这套定义高度同源。