题目重点：DoorDash Phone Coding 题解：两个 pickup 餐厅列表要保持各自顺序，找可共同前往的最长餐厅序列，使用 LCS 动态规划。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 把题目的“保持餐厅顺序”解释为两个列表中的相对顺序都不能改变，因此求最长公共子序列，而不是集合交集或连续公共子串。
- 餐厅名可在单个列表中重复，例程按每次出现的位置分别匹配；题目未明确重复餐厅是否可重复 pickup 的业务规则。
- 若有多个同长度最优答案，返回其中一个；题目未明确字典序或最早到达的平局条件。
解题路线
- 定义 dp[i][j] 为从第一列表 i 及第二列表 j 开始的最长共同路线长度。若两餐厅相同，可先共同访问它，再看 dp[i+1][j+1]；否则跳过任一侧当前餐厅，取较大值。
- 从后往前填表，再从 (0,0) 依表回溯出一条实际路线。两侧当前位置相同就选它，否则走到 dp 值不小的分支。
- 正确性由两种穷尽选择保证：任何共同路线第一步要么使用当前相同餐厅，要么至少跳过一侧当前餐厅；子问题边界为空表。
手动走一遍
司机 A 的路线 [A,B,C,D]，司机 B 的路线 [B,A,C,E,D]，可共同走 [A,C,D] 或 [B,C,D]，长度 3；只取共同餐厅集合 {A,B,C,D} 会错误忽略 A/B 的顺序冲突。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""One longest order-preserving route shared by two restaurant lists."""
def common_route(first: list[str], second: list[str]) -> list[str]:
n, m = len(first), len(second)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if first[i] == second[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
route: list[str] = []
i = j = 0
while i < n and j < m:
if first[i] == second[j]:
route.append(first[i])
i += 1
j += 1
elif dp[i + 1][j] >= dp[i][j + 1]:
i += 1
else:
j += 1
return route
复杂度
两个列表长度分别 n、m，DP 时间 O(nm)、空间 O(nm)，回溯 O(n+m)。若只求长度可滚动数组压到 O(min(n,m)) 空间；要输出路径需保留决策或用更复杂的重建算法。
易错点与追问
容易失分的边界
- 集合交集只判断是否出现，不保证两个司机都能按原列表顺序访问。
- 最长公共子串要求连续，但题目允许跳过无共同 pickup 的餐厅；应使用子序列。
- 没有在两个列表都消耗匹配位置就继续搜索，会把一次餐厅出现重复计入路线。
继续深挖
- 若同一餐厅物理位置但两个不同 pickup 任务，需用任务实例 ID 与餐厅 ID 区分，明确同店重复访问是否允许。
- 若还加入最短行车距离或时间窗，LCS 长度不再表达目标，状态需要位置/时间/路线成本，问题可能转成带约束路径优化。
