今天呢，上午还算是比较有空的，便是参加了一场 LeetCode 的周赛，而且还是第一次的周赛，体验还是挺不错的。

上午室友回家，我也是跟着醒的比较早，起床去吃个饭，回来后把宿舍打扫了一遍，以后一个半月这就是我一人的寝室了，妙，然后又去洗了洗衣服，堆了一旬的衣服，感觉再不洗就要发馊了，于是呢，便是搓搓揉揉，又是到了十点半。我一看表，呕吼，周赛要开始了，赶紧拿着电脑跑到了图书馆，其实宿舍也是可以打比赛的，可惜在宿舍学都学不下去，比赛也会不想打的。

到了图书馆已是十点四十五了，问题也不算太大，毕竟是佛系参赛选手，虽然是第一次。

现在呢，算是结束了，刚刚吃完午饭回来，还是写一下吧。

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 - c2) 。

请你返回你能得到的 最大 得分。

abs(x) 定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

1 2 3

1 5 1

3 1 1

输入：points = [[1,2,3],[1,5,1],[3,1,1]]
输出：9
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。

那么这一题要怎么求解呢？显而易见，这是一道动态规划问题。

用 $n$ 表示行数，$m$ 表示列数。

定义 $f[i][j]$ 表示前 $i$ 行中，第 $i$ 行选择 $\textit{points}[i][j]$ 时的最大得分，则有
$$
f[i][j]=points[i][j]+maxf[i−1][k]−∣k−j∣\tag{1}
$$
拆掉绝对值符号，将上式变形为
$$
f[i][j]=\left{
\begin{matrix}
points[i][j]+maxf[i−1][k]-(j-k), k\leq j\
points[i][j]+maxf[i−1][k]-(k-j), k> j\
\end{matrix}
\right.\tag{2}
$$
将 $j$ 提出来，化简为
$$
f[i][j]= \left { \begin{matrix}
points[i][j]−j+maxf[i−1][k]+k,{k\leq j}\
points[i][j]+j+maxf[i−1][k]−k,{k> j}\
\end{matrix} \right.\tag{3}
$$
由上式可知，在计算 $f[i][j]$ 时，我们需要知道位置 $j$ 左侧的 $f[i-1][k] + k$ 的最大值，以及位置 $j$ 右侧的 $f[i-1][k] - k$ 的最大值。这可以在计算完一整行 $f[i-1]$之后，在计算下一行 $f[i]$ 之前，预处理出来。

在实现的时候，$k \leq j$ 和 $k>j$ 可以分开来实现，对于 $k \leq j$，可事先让 $k$ 和 $j$ 都从 0 开始，使得 $k \leq j$；对于$k>j$ 则是可以使得 $k$ 从 $n-1$ 开始，而 $j$ 从 $n-2$ 开始，使得 $k>j$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m = len(points) # height
        n = len(points[0]) # width
        f = [[0]*n for i in range(m)]
        for i in range(n):
            f[0][i] = points[0][i]
        for i in range(1,m):
            ans = f[i-1][0]
            for j in range(n):# 从左到右
                ans = max(ans,f[i-1][j] + j) # 这里的 j 即为 k，k一定是小于等于 j 的
                f[i][j] = max(f[i][j],points[i][j] - j + ans)
            
            ans = f[i-1][n-1] - (n-1)
            for j in  range(n-2,-1,-1):# 从右到左
                f[i][j] = max(f[i][j], points[i][j] + j + ans)
                ans = max(ans, f[i-1][j] - j)# 这里的 j 即为 k，k一定是大于等于 j 的
        
        ans = 0
        for i in range(n):
            ans = max(ans,f[m-1][i])
        return ans

如图所示：