LeetCode 1937中等动态规划
扣分后的最大得分 图解题解
这道题到底在问什么
给定 m 行 n 列的整数矩阵 points。每一行选一个格子 (r, c),得分加上 points[r][c]。相邻两行 r 与 r+1 选的列 c1 与 c2,总分再扣掉 |c1 - c2|。返回能拿到的最大总分。
- 输入
- points=[[1,2,3],[1,5,1],[3,1,1]]
- 输出
- 9 (选列 1、列 1、列 0:2+5+3=10,扣 |1-1|+|1-0|=1,净得 9)
- 输入
- points=[[1,5],[2,3],[4,2]]
- 输出
- 11 (选列 1、列 1、列 0:5+3+4=12,扣 1,净得 11)
先想最直接的笨办法
核心就是这套:dp 逐行往下推,难点在那个绝对值。把它按方向拆成左右两段,各扫一遍取最大,就能把每格的枚举省成常数。下面把这套搬到表格上,一格一格看。（动画第 3 步）
最优解：一步一步想明白
- 3核心就是这套:dp 逐行往下推,难点在那个绝对值。把它按方向拆成左右两段,各扫一遍取最大,就能把每格的枚举省成常数。下面把这套搬到表格上,一格一格看。
- 4先看输入这就是输入矩阵 points,三行三列。规则再念一遍:每一行必须选一格,把分数加起来;相邻两行选的列号差多少,就扣多少。比如上一行选第 2 列、这一行选第 0 列,虽然分可能高,但要扣掉 2 分。接下来我们不再看原始分,而是把它变成一张 dp 表,记录每一格作为落脚点时的最优净得分。
- 5dp[0] 就位先填第 0 行。它上面没有别的行,不存在相邻行的扣分,所以在第 0 行落脚的最优得分就等于这一格本身的分数。dp 第 0 行直接抄下 points 第 0 行:1、2、3。这三个数是后面所有推导的地基,下面每一行都要踩着上一行往下算。
- 6朴素 O(n²) 太慢先看笨办法,好理解优化从哪来。想算 dp[1][1],也就是第 1 行落在第 1 列。它可以从上一行任意一列转过来,得分是上一行那格的 dp 减去两列的列号差。上一行第 0 列给 1 减 1 等于 0,第 1 列给 2 减 0 等于 2,第 2 列给 3 减 1 等于 2,取最大的 2,再加本格的 5,得到 7。问题是:每一格都这样枚举上一行全部列,一行 n 格就是 n 的平方,行多列多就慢了。
- 7左右两遍优化的钥匙就是那个绝对值。当上一行的列 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。两遍扫完,每格取较大的那个结果,枚举就省掉了。
- 8第 1 行 左扫中开始第 1 行的左扫,从第 0 列起。lmx 记的是上一行走到这里为止,dp[k] 加 k 的最大值。第 0 列只能看上一行第 0 列,lmx 就是 1。本格净得分等于本格分 1 加 lmx 再减去本列列号 0,算出 2,先落一个左扫的临时值。这只是考虑左边来源的临时值,右扫还要再比一次。
- 9第 1 行 左扫中往右挪到第 1 列。lmx 顺手把上一行第 1 列的 dp 加 1 也纳入比较,更新成 3,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 5 加 lmx 3 减列号 1,得到 7。这只是考虑左边来源的临时值,右扫还要再比一次。
- 10第 1 行 左扫中往右挪到第 2 列。lmx 顺手把上一行第 2 列的 dp 加 2 也纳入比较,更新成 5,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 5 减列号 2,得到 4。这只是考虑左边来源的临时值,右扫还要再比一次。
- 11第 1 行 右扫中右扫从最右一列往回走,先看第 2 列。rmx 更新到 1,右候选算出 4,和左扫的临时值 4 比一下取大的,这格定成 4。左边来源已经够好,值保持不变。
- 12第 1 行 右扫中右扫从最右一列往回走,到第 1 列。rmx 更新到 1,右候选算出 7,和左扫的临时值 7 比一下取大的,这格定成 7。左边来源已经够好,值保持不变。
- 13第 1 行 右扫打量右扫回到第 0 列。rmx 记的是上一行 dp[k] 减 k 的最大值,现在等于 1。它代表从右边某列斜过来的最好来源。本格右候选等于本格分 1 加 rmx 1 再加列号 0,等于 2。而它左扫时的临时值是 2。两个数摆在一起,下一帧见分晓,看右边的来源能不能把它抬高。
- 14第 1 行 右扫定案取两者较大:左扫的临时值 2 已经不小于右候选 2,所以第 0 列取较大后维持 2 不变。这一遍右侧来源没能超过它,但右扫这一遍仍不能省,换组数据右边就可能更优。这一格正式定案。
- 15第 1 行 就位第 1 行左右两遍都扫完了,三格的最优净得分定下来:2、7、4。注意第 1 列的 7,正是刚才朴素办法算出的那个 7,说明两遍扫描给出的结果和逐列枚举完全一致,只是快得多。这一行马上又成为下一行的上一行,继续往下推。
- 16第 2 行 左扫中开始第 2 行的左扫,从第 0 列起。lmx 记的是上一行走到这里为止,dp[k] 加 k 的最大值。第 0 列只能看上一行第 0 列,lmx 就是 2。本格净得分等于本格分 3 加 lmx 再减去本列列号 0,算出 5,先落一个左扫的临时值。这只是考虑左边来源的临时值,右扫还要再比一次。
- 17第 2 行 左扫中往右挪到第 1 列。lmx 顺手把上一行第 1 列的 dp 加 1 也纳入比较,更新成 8,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 8 减列号 1,得到 8。这只是考虑左边来源的临时值,右扫还要再比一次。
- 18第 2 行 左扫中往右挪到第 2 列。lmx 顺手把上一行第 2 列的 dp 加 2 也纳入比较,更新成 8,这正是它比一格一格枚举省事的地方,前面看过的最大值一路带着走。本格分 1 加 lmx 8 减列号 2,得到 7。这只是考虑左边来源的临时值,右扫还要再比一次。
- 19第 2 行 右扫中右扫从最右一列往回走,先看第 2 列。rmx 更新到 2,右候选算出 5,和左扫的临时值 7 比一下取大的,这格定成 7。左边来源已经够好,值保持不变。
- 20第 2 行 右扫中右扫从最右一列往回走,到第 1 列。rmx 更新到 6,右候选算出 8,和左扫的临时值 8 比一下取大的,这格定成 8。左边来源已经够好,值保持不变。
- 21第 2 行 右扫打量右扫回到第 0 列。rmx 记的是上一行 dp[k] 减 k 的最大值,现在等于 6。它代表从右边某列斜过来的最好来源。本格右候选等于本格分 3 加 rmx 6 再加列号 0,等于 9。而它左扫时的临时值是 5。两个数摆在一起,下一帧见分晓,看右边的来源能不能把它抬高。
- 22第 2 行 右扫定案取两者较大:右候选 9 比左扫的 5 更高,把它抬上来,第 0 列最终定成 9。看,右扫这一遍不是走过场,正是它把这格从 5 拉到了 9,说明这一格的最优来源在它右边那一列。这一格正式定案。
- 23第 2 行 就位第 2 行左右两遍都扫完了,三格的最优净得分定下来:9、8、7。这一行就是最后一行,每一格代表在这里收尾能拿到的最大净得分。答案就藏在这三个数里。
- 24答案 = 9最后一行填的是走到底、分别落在各列时的最优净得分。我们可以在最后一行的任意一列收尾,所以答案就是这一行里最大的那个数。三个数 9、8、7 里,第 0 列的 9 最大,这就是最终答案。
- 25路径净得 = 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 表和真实选法对上了。
⚠️ 容易写错的地方
✗ 错：每格都枚举上一行所有列取最大
✓ 对：把绝对值拆成左右两段,各用一遍前缀最大值
直接枚举是 O(m·n²),数据一大就超时;拆方向后每行两遍线性扫描降到 O(m·n)
✗ 错：绝对值不拆方向直接算 |c-k|
✓ 对：按 k≤c 与 k≥c 拆成 c-k 与 k-c 两段
不拆方向就没法把式子整理成只与 dp[k]+k 或 dp[k]-k 有关,也就用不上前缀最大值优化
✗ 错：用 int 存 dp 和累加值
✓ 对：C 加加用 long long、Java 用 long
行列规模和分值都可达十万量级,累加会超出 int 范围溢出,Python 整数天然不溢出
✗ 错：只做左扫或只做右扫就取值
✓ 对：左右两遍都做,每格取两者较大
最优来源可能在当前列的左边也可能在右边,漏掉一侧就会少算,必须两遍都比
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points[0])
f = points[0][:]
for p in points[1:]:
g = [0] * n
lmx = -inf
for j in range(n):
lmx = max(lmx, f[j] + j)
g[j] = max(g[j], p[j] + lmx - j)
rmx = -inf
for j in range(n - 1, -1, -1):
rmx = max(rmx, f[j] - j)
g[j] = max(g[j], p[j] + rmx + j)
f = g
return max(f)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
using ll = long long;
int n = points[0].size();
vector<ll> f(n);
const ll inf = 1e18;
for (auto& p : points) {
vector<ll> g(n);
ll lmx = -inf, rmx = -inf;
for (int j = 0; j < n; ++j) {
lmx = max(lmx, f[j] + j);
g[j] = max(g[j], p[j] + lmx - j);
}
for (int j = n - 1; ~j; --j) {
rmx = max(rmx, f[j] - j);
g[j] = max(g[j], p[j] + rmx + j);
}
f = move(g);
}
return *max_element(f.begin(), f.end());
}
};Java
import java.util.*;
class Solution {
public long maxPoints(int[][] points) {
int n = points[0].length;
long[] f = new long[n];
final long inf = 1L << 60;
for (int[] p : points) {
long[] g = new long[n];
long lmx = -inf, rmx = -inf;
for (int j = 0; j < n; ++j) {
lmx = Math.max(lmx, f[j] + j);
g[j] = Math.max(g[j], p[j] + lmx - j);
}
for (int j = n - 1; j >= 0; --j) {
rmx = Math.max(rmx, f[j] - j);
g[j] = Math.max(g[j], p[j] + rmx + j);
}
f = g;
}
long ans = 0;
for (long x : f) {
ans = Math.max(ans, x);
}
return ans;
}
}复杂度
时间
O(m·n)
m 行,每行做左、右两遍长度为 n 的线性扫描,每格只做常数次比较与加减,总量随格子数线性增长。相比朴素每格枚举上一行 n 列的 O(m·n²),省掉了一层
空间
O(n)
按峰值算。只需保存上一行 dp 和当前行 dp 两个长度为 n 的数组滚动使用,不必存整张 m 行的表,所以是 O(n) 而不是 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 扣分后的最大得分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题最直接的 DP 怎么写,瓶颈在哪?+
定义 dp[r][c] 为第 r 行落在第 c 列时的最大净得分,转移是 dp[r][c] = points[r][c] 加上上一行某列 k 的 dp[r-1][k] 再减 |c-k|。最直接的写法是每格枚举上一行全部 n 列取最大,复杂度 O(m·n²),瓶颈就在这层枚举,数据规模到十万级会超时。
怎么优化到线性?+
把 |c-k| 按方向拆开。k 在 c 左边时列号差是 c-k,转移里出现的是 dp[k]+k 减 c,从左往右扫维护 dp[k]+k 的最大值 lmx;k 在右边时是 dp[k]-k 加 c,从右往左扫维护 dp[k]-k 的最大值 rmx。每格取左右两遍的较大值,一行两遍线性扫描,总复杂度降到 O(m·n)。
空间和数值上要注意什么?+
空间上只需滚动保存上一行和当前行两个长度 n 的数组,是 O(n)。数值上得分会累加到很大,C 加加用 long long、Java 用 long 防止 int 溢出,哨兵负无穷要取足够小的负值(也就是绝对值足够大的负数),写成正的会让左右两遍扫描被虚假的超大值污染,Python 整数不溢出可直接用负无穷。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 扣分后的最大得分 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。