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