扣分后的最大得分 图解题解

每行选一格还要扣列号差，这题在权衡什么

给 m 行 n 列的矩阵 points，格子记作 (r,c)（行号、列号，从 0 数起）。每行必须选一格，把 points[r][c] 加进总分；相邻两行选的列号差多少就扣多少。想选大分，又想列对齐少扣分，得两头权衡。

每格回头扫上一行整排，O(m·n²) 的账怎么算

第 r 行落在哪格只受上一行落点影响，正好用逐行的动态规划（DP，把「第 r 行落在第 c 列」的最优净得分记成 dp[r][c]，推下一行直接取）。转移（由上一行推出这一行的式子）：dp[r][c]=points[r][c]+max(dp[r-1][k]-|c-k|)，k 取遍上一行各列。

麻烦在 max：每格要枚举上一行整排，一行 n 格就是 n²，m 行合计 O(m·n²)（大 O 描述输入变大时计算量怎么涨），行列一多跑不动。

|c-k| 把两个列号绑在一起，怎么按方向拆开

绝对值同时牵着 c 和 k。k 在 c 左边（k≤c）时 |c-k|=c-k，候选变成 dp[r-1][k]+k-c，对固定的 c 只需左侧 dp[r-1][k]+k 的最大值；k 在右边时 |c-k|=k-c，只需右侧 dp[r-1][k]-k 的最大值。两边要的都是前缀最大值（扫到当前列为止见过的最大值），一遍扫描带着走。

lmx、rmx 各扫一遍，k=c 算两次要不要紧

从左往右扫：到第 c 列先把 dp[r-1][c]+c 并入 lmx（lmx=左侧 dp[r-1][k]+k 的最大值，开局设负无穷；rmx 同理管右侧），落左候选 points[r][c]+lmx-c；再从右往左维护 rmx，落右候选 points[r][c]+rmx+c，每格取较大者。k=c 两遍都算，差是 0、候选相同，重复无妨。第 0 行没上一行，直接抄 points 首行。

三行三列的示例，两遍扫描各扫出什么

示例 [[1,2,3],[1,5,1],[3,1,1]]，第 0 行照抄 dp=[1,2,3]。第 1 行左扫：lmx 依次 1、max(1,2+1)=3、5，左候选 1+1-0=2、5+3-1=7、1+5-2=4；右扫：rmx 依次 1、1、1，右候选 4、7、2（按扫描方向、即从右往左列），都没超过，第 1 行定成 [2,7,4]。

第 2 行左扫：lmx 依次 2、8、8，左候选 3+2-0=5、1+8-1=8、1+8-2=7；右扫：rmx 依次 2、6、6，右候选 1+2+2=5、1+6+1=8、3+6+0=9，第 0 列的 5 被 9 换掉。末行 [9,8,7]，最大 9 即答案：三行选列 1、列 1、列 0，2+5+3=10 扣 |1-1|+|1-0|=1。

rmx 初值偷懒写成 0，答案为什么会虚高

rmx 记的 dp[r-1][k]-k 可能是负数；初值写 0 等于捏造不存在的来源，答案跟着虚高。哨兵（绝不会被选上的极小初值）得够小，Python 用负无穷；总分会越加越大，C++ 要 long long、Java 要 long。

时间 O(m·n)，每行左右各扫一遍；空间 O(n)，只留上一行、当前行两个数组滚动。单行没有相邻行，答案是首行最大值。

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;
    }
}