扣分后的最大得分

核心就是这套:dp 逐行往下推,难点在那个绝对值。把它按方向拆成左右两段,各扫一遍取最大,就能把每格的枚举省成常数。下面把这套搬到表格上,一格一格看。

输入 points · 每行挑一格：这就是输入矩阵 points,三行三列。规则再念一遍:每一行必须选一格,把分数加起来;相邻两行选的列号差多少,就扣多少。比如上一行选第 2 列、这一行选第 0 列,虽然分可能高,但要扣掉 2 分。接下来我们不再看原始分,而是把它变成一张 dp 表,记录每一格作为落脚点时的最优净得分。

dp 第 0 行 = points 第 0 行：先填第 0 行。它上面没有别的行,不存在相邻行的扣分,所以在第 0 行落脚的最优得分就等于这一格本身的分数。dp 第 0 行直接抄下 points 第 0 行:1、2、3。这三个数是后面所有推导的地基,下面每一行都要踩着上一行往下算。

朴素想法 · 枚举上一行每一列：先看笨办法,好理解优化从哪来。想算 dp[1][1],也就是第 1 行落在第 1 列。它可以从上一行任意一列转过来,得分是上一行那格的 dp 减去两列的列号差。上一行第 0 列给 1 减 1 等于 0,第 1 列给 2 减 0 等于 2,第 2 列给 3 减 1 等于 2,取最大的 2,再加本格的 5,得到 7。问题是:每一格都这样枚举上一行全部列,一行 n 格就是 n 的平方,行多列多就慢了。

拆绝对值 · 左右各扫一遍：优化的钥匙就是那个绝对值。当上一行的列 k 在当前列 c 的左边,也就是 k 不大于 c,列号差就是 c 减 k,把它塞进转移里整理一下,只跟 dp[k] 加 k 有关,对固定的 c 来说 c 是常数。于是从左往右扫,维护一个 dp[k] 加 k 的最大值 lmx,每格拿它减去 c 就行。反过来,k 在右边时列号差是 k 减 c,只跟 dp[k] 减 k 有关,再从右往左扫一遍,维护 dp[k] 减 k 的最大值 rmx。两遍扫完,每格取较大的那个结果,枚举就省掉了。

第 1 行 左扫 · 落第 0 列：开始第 1 行的左扫,从第 0 列起。lmx 记的是上一行走到这里为止,dp[k] 加 k 的最大值。第 0 列只能看上一行第 0 列,lmx 就是 1。本格净得分等于本格分 1 加 lmx 再减去本列列号 0,算出 2,先落一个左扫的临时值。这只是考虑左边来源的临时值,右扫还要再比一次。

第 1 行 左扫 · 落第 1 列：往右挪到第 1 列。lmx 顺手把上一行第 1 列的 dp 加 1 也纳入比较,更新成 3,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 5 加 lmx 3 减列号 1,得到 7。这只是考虑左边来源的临时值,右扫还要再比一次。

第 1 行 左扫 · 落第 2 列：往右挪到第 2 列。lmx 顺手把上一行第 2 列的 dp 加 2 也纳入比较,更新成 5,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 5 减列号 2,得到 4。这只是考虑左边来源的临时值,右扫还要再比一次。

第 1 行 右扫 · 第 2 列 = 4：右扫从最右一列往回走,先看第 2 列。rmx 更新到 1,右候选算出 4,和左扫的临时值 4 比一下取大的,这格定成 4。左边来源已经够好,值保持不变。

第 1 行 右扫 · 第 1 列 = 7：右扫从最右一列往回走,到第 1 列。rmx 更新到 1,右候选算出 7,和左扫的临时值 7 比一下取大的,这格定成 7。左边来源已经够好,值保持不变。

第 1 行 右扫 · 打量第 0 列：右扫回到第 0 列。rmx 记的是上一行 dp[k] 减 k 的最大值,现在等于 1。它代表从右边某列斜过来的最好来源。本格右候选等于本格分 1 加 rmx 1 再加列号 0,等于 2。而它左扫时的临时值是 2。两个数摆在一起,下一帧见分晓,看右边的来源能不能把它抬高。

第 1 行 右扫 · 第 0 列定案 = 2：取两者较大:左扫的临时值 2 已经不小于右候选 2,所以第 0 列取较大后维持 2 不变。这一遍右侧来源没能超过它,但右扫这一遍仍不能省,换组数据右边就可能更优。这一格正式定案。

第 1 行 填完 · dp = [2, 7, 4]：第 1 行左右两遍都扫完了,三格的最优净得分定下来:2、7、4。注意第 1 列的 7,正是刚才朴素办法算出的那个 7,说明两遍扫描给出的结果和逐列枚举完全一致,只是快得多。这一行马上又成为下一行的上一行,继续往下推。

第 2 行 左扫 · 落第 0 列：开始第 2 行的左扫,从第 0 列起。lmx 记的是上一行走到这里为止,dp[k] 加 k 的最大值。第 0 列只能看上一行第 0 列,lmx 就是 2。本格净得分等于本格分 3 加 lmx 再减去本列列号 0,算出 5,先落一个左扫的临时值。这只是考虑左边来源的临时值,右扫还要再比一次。

第 2 行 左扫 · 落第 1 列：往右挪到第 1 列。lmx 顺手把上一行第 1 列的 dp 加 1 也纳入比较,更新成 8,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 8 减列号 1,得到 8。这只是考虑左边来源的临时值,右扫还要再比一次。

第 2 行 左扫 · 落第 2 列：往右挪到第 2 列。lmx 顺手把上一行第 2 列的 dp 加 2 也纳入比较,更新成 8,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 8 减列号 2,得到 7。这只是考虑左边来源的临时值,右扫还要再比一次。

第 2 行 右扫 · 第 2 列 = 7：右扫从最右一列往回走,先看第 2 列。rmx 更新到 2,右候选算出 5,和左扫的临时值 7 比一下取大的,这格定成 7。左边来源已经够好,值保持不变。

第 2 行 右扫 · 第 1 列 = 8：右扫从最右一列往回走,到第 1 列。rmx 更新到 6,右候选算出 8,和左扫的临时值 8 比一下取大的,这格定成 8。左边来源已经够好,值保持不变。

第 2 行 右扫 · 打量第 0 列：右扫回到第 0 列。rmx 记的是上一行 dp[k] 减 k 的最大值,现在等于 6。它代表从右边某列斜过来的最好来源。本格右候选等于本格分 3 加 rmx 6 再加列号 0,等于 9。而它左扫时的临时值是 5。两个数摆在一起,下一帧见分晓,看右边的来源能不能把它抬高。

第 2 行 右扫 · 第 0 列定案 = 9：取两者较大:右候选 9 比左扫的 5 更高,把它抬上来,第 0 列最终定成 9。看,右扫这一遍不是走过场,正是它把这格从 5 拉到了 9,说明这一格的最优来源在它右边那一列。这一格正式定案。

第 2 行 填完 · dp = [9, 8, 7]：第 2 行左右两遍都扫完了,三格的最优净得分定下来:9、8、7。这一行就是最后一行,每一格代表在这里收尾能拿到的最大净得分。答案就藏在这三个数里。

取末行最大值 · 答案 = 9：最后一行填的是走到底、分别落在各列时的最优净得分。我们可以在最后一行的任意一列收尾,所以答案就是这一行里最大的那个数。三个数 9、8、7 里,第 0 列的 9 最大,这就是最终答案。

回看这条最优路径：倒回去看它是怎么长出来的。末行第 0 列的 9,是右扫时从第 1 行第 1 列的 7 转过来的;那个 7 又是从第 0 行第 1 列的 2 接上来的。对应到原始选格,就是第 0 行选第 1 列拿 2,第 1 行选第 1 列拿 5,第 2 行选第 0 列拿 3,原始分共 10,扣掉列号差 0 加 1 等于 1,净得 9。上一行选第 2 列拿 3 也能并列得到同样的 9,殊途同归。这条链子把 dp 表和真实选法对上了。

边界想清:单行直接取行内最大、单列被迫同列不扣分求和、一般情形要在得分与列号差之间权衡。

面试三连:朴素 DP 及其瓶颈、拆绝对值加前缀最大值降到线性、滚动数组省空间与 long 防溢出。