设计一个算法解决竞赛中的动态规划问题（如最长公共子序列），并解释状态转移方程、边界条件，以及如何优化空间复杂度。
学而思竞赛教练（理科、C++）难度：中等
答案
1) 【一句话结论】解决最长公共子序列（LCS）问题，可通过动态规划定义状态为前i个字符与前j个字符的LCS长度，状态转移方程为字符相等时加1，否则取前缀最大值，边界为初始全0，空间优化通过滚动数组将O(mn)空间降为O(n)。
2) 【原理/概念讲解】
老师：我们以最长公共子序列为例，核心是定义状态并推导转移。设字符串a长度为m，b长度为n，定义dp[i][j]为a的前i个字符（a[0..i-1]）和b的前j个字符（b[0..j-1]）的最长公共子序列（LCS）长度。
类比：就像拼图，每一步看当前字符是否匹配，匹配则“拼上”，否则从左边或上边找最长。
状态转移方程：
- 若a[i-1] == b[j-1]，则当前字符匹配，LCS长度为前缀的LCS加1，即
dp[i][j] = dp[i-1][j-1] + 1； - 否则不匹配，取不匹配前缀的最大LCS，即
dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
边界条件：当i=0或j=0时，dp[0][*]=0、dp[*][0]=0（空字符串与任何字符串的LCS长度为0）。
空间优化：由于dp[i][j]仅依赖上一行（dp[i-1][*]），可用一维数组滚动，将空间复杂度从O(mn)降至O(n)，时间复杂度仍为O(mn)。
3) 【对比与适用场景】
| 比较项 | 最长公共子序列（LCS） | 最长公共子串（Longest Common Substring） |
|---|---|---|
| 定义 | 不要求字符连续 | 要求字符连续（原字符串中位置相邻） |
| 状态转移 | dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]) | dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : 0（不连续则重置） |
| 空间优化 | 一维滚动数组（O(n)） | 通常需二维（连续性依赖对角线） |
| 适用场景 | 文本匹配、序列比对（如DNA序列） | 检测连续匹配（如字符串搜索） |
4) 【示例】
字符串a="ABCBDAB"，b="BDCABA"，计算LCS。
伪代码：
m, n = len(a), len(b)
dp = [0] * (n+1)
for i in range(1, m+1):
prev = 0 # 上一行第一个元素（初始为0）
for j in range(1, n+1):
temp = dp[j] # 保存当前dp[j]，用于下一轮更新
if a[i-1] == b[j-1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j-1])
prev = temp # 更新prev为上一行当前j的值
print(dp[n]) # 结果为4（LCS为"BCBA"或"BDAB"等）
5) 【面试口播版答案】
您好，针对最长公共子序列问题，核心思路是用动态规划定义状态为前i个字符和前j个字符的LCS长度。设字符串a长度为m，b长度为n，dp[i][j]表示a前i个与b前j个的LCS长度。状态转移方程：若a[i-1]等于b[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则取dp[i-1][j]和dp[i][j-1]的最大值。边界条件是i或j为0时，dp值为0（空字符串与任何字符串的LCS为0）。空间优化通过一维数组滚动，将空间复杂度从O(mn)降至O(n)，时间复杂度保持O(mn)。这样就能高效计算最长公共子序列的长度。
6) 【追问清单】
- 问：为什么可以用一维数组优化空间？
答：因为dp[i][j]仅依赖上一行（dp[i-1][*]）和当前列前一个元素（dp[i][j-1]），只需保留上一行和当前行数据，实现滚动。 - 问：时间复杂度是多少？
答：O(mn)，每个状态计算一次，总共有mn个状态。 - 问：边界条件如何处理？
答：i=0或j=0时，dp值为0，这是递归的基例（空字符串与任何字符串的LCS为0）。 - 问：字符串很长（如m、n达10^5）怎么办？
答：空间优化后空间为O(n)，时间O(mn)仍可行；若需进一步优化，可考虑DP+优化或记忆化搜索，但基本DP复杂度是O(mn)。 - 问：LCS和子串有什么区别？
答：子串要求字符在原字符串中连续，而子序列不要求，比如“ABC”和“AC”的子序列是“AC”，但子串需连续，原字符串中无连续“AC”，故LCS为“AB”或“BC”，子串可能不存在。
7) 【常见坑/雷区】
- 状态定义错误：误将
dp[i][j]定义为子串长度，导致转移方程错误。 - 边界条件遗漏：初始化为1或错误值，导致结果偏大。
- 空间优化错误：未正确更新上一行数据，导致
dp值计算错误。 - 混淆子序列与子串：误用子串的转移方程计算LCS，结果不正确。
- 时间复杂度分析错误：认为空间优化后时间复杂度降低，实际上时间复杂度不变。