最长公共子串的DP状态定义为dpi表示以s1[i-1]和s2[j-1]结尾的最长公共子串长度，转移方程为：相等时dpi=dpi-1+1，否则为0，需实时更新全局最大值。
最长公共子串的动态规划状态怎么定义
子串必须连续，所以状态不能只记“前i个和前j个字符的LCS长度”——那是最长公共子序列（LCS）的定义。最长公共子串（Longest Common Substring）的状态得体现“以
和
结尾”这个关键约束。
因此定义
为：以
和
结尾的最长公共子串长度。注意下标偏移，避免边界判断爆炸。
如果
，则
否则
（子串断了，必须归零）
全局最大值在每次更新
时同步记录，不能最后扫一遍矩阵——因为有效解只出现在非零连续段上
二维DP数组要不要真的开m×n大小
转移只依赖上一行左上角，理论上可以空间优化到一维。但真这么干容易出错：你得用临时变量存
，而普通滚动数组会覆盖掉它。
实际开发中，除非字符串长达10⁵级且内存敏感，否则直接用二维列表更稳。Python里
清晰不易错。
立即学习
“
Python免费学习笔记（深入）
”；
用
而不用
：小规模字符串没必要引入依赖，且
的
在超长串下可能溢出
初始化全0，第一行第一列天然对应空字符串匹配，无需特殊处理
别用
—— 这是浅拷贝，改一行全变
边界条件和空字符串怎么处理
空字符串的最长公共子串长度就是0，这和
初始全0完全一致，所以不需要 if 分支预判空输入。
Python 3.14.3
微软官方的 Python 扩展，是 VS Code 安装量最高的扩展（209M+）。集成 IntelliSense（通过 Pylance）、调试（通过 Python Debugger）、代码检查、格式化、重构和单元测试等功能。支持 Jupyter Notebook、虚拟环境管理和多 Python 版本切换。
下载
但要注意：当任意一个字符串为空时，循环范围会退化，
自然不执行，最终返回0，逻辑自洽。
测试用例务必包含：
、
、
、
、
和
（答案是3，不是4）
别在循环里写
—— 初始化已覆盖，多此一举还易漏更新
返回的是长度，不是子串本身；若需子串，得额外记下最大值出现时的
，再用
截取
为什么不能用递归+记忆化直接套用LCS模板
因为子串的“连续性”约束让递归分支大幅受限：一旦字符不等，当前路径就彻底终止，无法像LCS那样尝试“跳过s1[i]”或“跳过s2[j]”。
强行递归不仅没优势，还容易写出错误的状态转移，比如写成
—— 这已经是在算LCS了。
动态规划的转移方程是确定的：
没有其他分支，没有“选或不选”，也没有后效性需要回溯
递归写法反而要多传两个参数（当前匹配长度），不如迭代直观
实际写的时候，最常漏的是更新全局最大值的时机——必须在
时立刻比对，而不是等循环结束再找矩阵最大值。矩阵里大量0值会让
看似省事，但一旦字符串含大量重复字符（比如全是'a'），
最后一行全是递增数，max操作本身变成O(mn)，白费了DP的O(mn)时间保证。
s1[i]s2[j]dp[i][j]s1[i-1]s2[j-1]s1[i-1] == s2[j-1]dp[i][j] = dp[i-1][j-1] + 1dp[i][j] = 0dp[i][j]dp[i-1][j-1][[0] * (len(s2)+1) for _ in range(len(s1)+1)]listnumpynumpyint32dp = [[0]*(n+1)]*(m+1)dprange(1, len(s1)+1)s1=""s2=""s1="a"s2="a"s1="abab"s2="baba"if i==0 or j==0: continueis1[i-max_len:i]max(dfs(i-1,j), dfs(i,j-1))dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1]==s2[j-1] else 0dp[i][j] > 0max(map(max, dp))dp