1537. 最大得分
考点
- 状态机DP
- 双指针
- 状态设计
最大得分路径合并：值轴 DP 与三种转移情况
题目要求：给定两个严格递增数组 nums1 和
nums2，我可以从任意一个数组的开头出发，向右走，每走到一个元素就把它的值加到总和里；当两个数组出现相同的数时，我可以在这个数上“换轨”（从数组
1 换到数组 2，或者反过来），换轨不扣分，目标是最大化总和，答案最后对
1e9+7 取模。
这道题我使用的是“在值域上合并 + 二维 DP”的思路。
1. 值轴与点阵图建模
由于两个数组都是严格递增，我可以把它们看成在同一条“值轴”上前进。
举一个具体例子：
1 | nums1 = [1, 4, 5] |
把两个数组出现过的所有数合并、排序，得到值轴： \[ v_1 = 1,\ v_2 = 2,\ v_3 = 3,\ v_4 = 4,\ v_5 = 5 \] 我画成一个“点阵图”（● 表示该数组在这一列有这个数，. 表示没有）：
1 | 值: 1 2 3 4 5 |
- 第 1 列（值 1）：两个数组都有 → “交点”
- 第 2 列（值 2）：只有
nums2有 - 第 3 列（值 3）：只有
nums2有 - 第 4 列（值 4）：只有
nums1有 - 第 5 列（值 5）：两个数组都有 → “交点”
在这个点阵图上，我的移动规则是：
- 在同一行向右走，相当于沿同一个数组往后取元素
- 在某一列的上下两个点之间上下切换，相当于在相同元素处换轨
所以问题等价于： 在这个“二行多列”的点阵图上，从第 1 列开始，到最后一列结束，允许在有两颗点的列上下切换，求一条得分最大的路径。
2. DP 状态设计
我用一维列索引来做 DP。记“合并后的第 \(k\) 列”为一个位置。
- \(f[k][0]\)：考虑到第 \(k\) 列，且停在
nums1这一行的最大得分 - \(f[k][1]\)：考虑到第 \(k\) 列，且停在
nums2这一行的最大得分
初始条件： \[ f[0][0] = f[0][1] = 0 \] 第 0 列可以理解为“还没走任何数时”的起点，得分为 0。
最终答案取： \[
\max(f[K][0], f[K][1]) \bmod (10^9 + 7)
\] 在代码里，我用一个游标 i
表示当前是“合并后的第几列”，这个 i 就对应上面的 \(k\)。
3. 三种情况的转移与点阵示意
在每一列，根据点阵的形状只有三种可能情况：
- 这一列只有
nums1有这个数 - 这一列只有
nums2有这个数 - 这一列两个数组都有这个数（交点，可换轨）
下面我分三种情况写出点阵图和转移方程，并对应到我的代码。
3.1 情况一：只有 nums1
有当前值
点阵图是：
1 | nums1: ● |
解释：当前值只出现在 nums1 中，因此：
- 停在
nums1的状态，要在上一列的nums1状态基础上加上当前值 - 停在
nums2的状态，只能把上一列的nums2状态“平移”过来，不加分
转移方程： \[
\begin{aligned}
f[k][0] &= f[k-1][0] + v_k, \\
f[k][1] &= f[k-1][1].
\end{aligned}
\]
对应到代码，就是这一段（nums1[l1 - 1] < nums2[l2 - 1]
的分支）：
1 | while (l1 <= n1 && (l2 > n2 || nums1[l1 - 1] < nums2[l2 - 1])) { |
3.2 情况二：只有 nums2
有当前值
点阵图：
1 | nums1: . |
和情况一完全对称，这一列的值只出现在 nums2，所以：
- 停在
nums2的状态，在上一列的nums2状态基础上加当前值 - 停在
nums1的状态，只能把上一列nums1的状态“平移”过来
转移方程： \[
\begin{aligned}
f[k][1] &= f[k-1][1] + v_k, \\
f[k][0] &= f[k-1][0].
\end{aligned}
\] 对应代码（nums2[l2 - 1] < nums1[l1 - 1]
的分支）：
1 | while (l2 <= n2 && (l1 > n1 || nums2[l2 - 1] < nums1[l1 - 1])) { |
3.3 情况三：交点，两边都有当前值
点阵图：
1 | nums1: ● |
当前值同时出现在 nums1 和 nums2
中，这是一个可以自由换轨的交点。
在这一列，我可以：
- 从上一列的
nums1走到nums1当前列 - 或从上一列的
nums2切换到nums1当前列 - 同理，也可以从上一列的任意一行到当前
nums2行
无论最后停在上面还是下面，这一列的最大得分一定是“上一列两行的较大值 + 当前值”。
设 \[ \text{best}_{k-1} = \max\bigl(f[k-1][0],\ f[k-1][1]\bigr), \] 则转移为： \[ \begin{aligned} f[k][0] &= \text{best}_{k-1} + v_k, \\ f[k][1] &= \text{best}_{k-1} + v_k. \end{aligned} \] 也就是两行在交点处会“同步”成同一个最大值。
对应代码（nums1[l1 - 1] == nums2[l2 - 1] 的分支）：
1 | while (l1 <= n1 && l2 <= n2 && nums2[l2 - 1] == nums1[l1 - 1]) { |
这里用 f[i][1] = f[i][0] = ... 实现了“同步”的效果。
4. 我在实现中遇到的取模问题
题目要求输出结果对 mod = 1e9+7 取模，最开始我容易写成“DP
过程中每一步都取模”，例如下面这种风格：
1 | //（错误写法示意，不是 AC 代码） |
这样会有一个非常隐蔽的问题： 我在交点做比较
max(f[i-1][0], f[i-1][1])
时比较的是“取模后的值”，不是“真实累加和”，可能把原本更大的路径“压小”了，从而选错路径。
4.1 为何中途取模会出错
举一个极端但清晰的例子：
假设在某一列之前，真实的 DP 值是： \[
f[i-1][0] = 1.5\times10^9,\quad f[i-1][1] = 8\times10^8.
\] 真实情况下，显然应该认为： \[
f[i-1][0] > f[i-1][1],
\] 在交点处，应该从 f[i-1][0] 那条路径转移。
但如果我每一步都 % mod，取
mod = 10^9 + 7，那么 \[
1.5\times10^9 \bmod (10^9+7) = 5\times10^8 - 7 \quad (\text{大约 }
499999993),
\] 于是取模后的数变成了： \[
f[i-1][0]^{\text{(mod)}} \approx 5\times10^8,
\quad
f[i-1][1]^{\text{(mod)}} = 8\times10^8,
\] 这时比较就变成了： \[
f[i-1][1]^{\text{(mod)}} > f[i-1][0]^{\text{(mod)}}.
\]
结果在交点处，我会错误地选择原本“路径和更小”的那一条，这等于把后面所有决策都建立在一个错误的基础上，最终答案也就错了。
4.2 正确处理方式
为了既避免溢出，又不破坏 DP 决策，我的做法是：
- 使用
long long存 DP 数组，保证在测试数据范围内不溢出 - DP 过程中严格不取模，所有比较都在真实累加和上做
- 只有在最终返回答案时，才对结果取一次模
对应到 AC 代码的尾部：
1 | return max(f[i][0], f[i][1]) % mod; |
这里的 f[i][0] 和 f[i][1] 都是用
long long 保存的真实路径和，最后统一
% mod，既安全又不会影响路径选择。
5. 完整 AC 代码（附注）
最后附上我这份 AC 的实现，方便读者对照 DP 推导理解：
1 | class Solution { |
滚动数组版：
1 | class Solution { |