今天呢，上午还算是比较有空的，便是参加了一场 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\) 。

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

如图所示：