题目重点：Applied Research OA 题目变体提数字与 +/− 矩阵；完整表达式可在任意格结束，另帖说不许转弯，须区分两种路径版本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练主版本允许每步向右或向下、可转弯；单个数字合法，表达式必须以数字开头和结束，算术从左到右，因为只有 +/−。
- 可从任意数字格开始，在任意数字格结束；不能将两个数字当多位数，也不能跳格；题目没给括号。
- 分支版本若不许转弯，则路径一旦选横/纵，后续必须保持，需按行/列连续片段分别计算。
- 输入矩阵为非空矩形；如果没有数字则无合法表达式，返回 None/错误的实际格式需现场确认。
解题路线
- 把状态分成 D[i,j]（在数字格结束的最大完整值）、P[i,j]（走到 + 后等待数字的最大前缀值）、M[i,j]（走到 − 后等待数字的最大前缀值），不可达置 −∞。
- 处理数字 d 时可新开表达式得 d，或从上/左相邻的 P 得 P+d、从 M 得 M−d；取三者最大。处理 +/− 格时只从上/左的 D 转移到对应待操作符状态。
- 因为未来只会对当前值加减一个固定数字，较大前缀在所有后续路径仍不劣，所以每个状态只存最大值足够；若引入乘法、括号或负号作一元运算，这个单最大不变量不再可靠。
- 遍历每格的 D 更新全局最大，不只看终点右下角。若面试明确不许转弯，用同一有限状态机分别扫描每行与每列的连续片段，不能让上/左状态跨方向汇合。
- 测试单数字、无数字、连续符号、连续数字、负结果、最大值在中间、转弯优于直线与严格无转弯变体。
手动走一遍
一行 [2,+,3,−,1] 的完整值有 2、3、1、2+3=5、3−1=2、2+3−1=4，最大为 5；因此不能强制路径到末端。若矩阵中最佳表达式需右→下转弯，主版本可取，no-turn 版本不可取，题面要先确认。
规模与取舍
R×C 格每格常数个转移，O(RC) 时间、O(RC) 空间；仅依赖上行/当前行可滚动到 O(C) 状态空间，仍需全局答案。无转弯版本逐行逐列扫描亦 O(RC) 时间。
易错点与追问
容易失分的边界
- 允许两个数字或两个运算符相邻。
- 只返回右下角 DP，而最大子表达式可以提前结束。
- 把 的不可转弯约束忽略，或把它加到所有题目描述。
- 从符号格开始或以符号格结束也当合法。
- 把 − 操作误写成相邻数字−前缀。
继续深挖
- 允许括号或乘法时要保存哪些额外状态？
- 如何返回达到最大值的具体路径？
- 有障碍/不可走格时怎样处理？
- 若路径必须从左上走到右下怎样改？
