题解

核心算法

dp[i][j] 表示两个前缀的答案；末字符相同则同时取，不同则舍弃一个末字符。

思路推导

两种转移覆盖所有公共子序列末尾情况。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(nm)
• 空间复杂度：O(m)

易错点

公共子串与公共子序列不可混淆；滚动数组要先清零。

完整标程见 std/main.cpp。