题目来自 Leetcode 的 5815 题。

题目的核心是：从二维矩阵中的每行中选取一个格子，每次选择一个格子后，所累计的最新积分等于前面已获积分加上被选格子的分数减去上一个格子和当前被选格子的列差。用公式表达更清晰：

points // 表示 m x n 的二维矩阵每个格子的分数
score(r, c) // 表示选取到 r 行 c 列所获得的最大得分
score(r+1, c^) = score(r, c) + points[r+1, c^] - abs(c - c^)

通过这个关系，可以确定两个事情：

1. 这是一个典型的动态规划问题：问题的最优解依赖子问题的最优解，且子问题的最优解相互影响，这一点是和贪心算法最大的不同；
2. 在为每一行选择一个格子时，要使 score(r+1, c^) 的值最大，需要找到一对特殊的 (c, c^) 的值，这也就是意味着：每次在为每一行挑选最优的格子时，需要针对结合上一行的每一列，与当前行的每一列，找出最优组合。

按照这个思路来写代码的话，整个算法的时间复杂度是 O(RC²)，空间复杂度是 O(C)。直接提交，会触发 TLE（Time Limit Exceed）。

优化思路

回到最开始列的式子那里，调整式子的写法：

score(r+1, c^) = score(r, c) - abs(c-c^) + points[r+1, c^]

可见，其中 points[r+1, c^] 是不变量，要使 score(r+1, c^) 的值最大，只需要满足 score(r, c) - abs(c-c^) 最大即可。

由于 abs(c-c^) 表示相邻两行的两个格子的列差，(c-c^)的正负结果受两者的相对位置关系影响，于是，我们分开两种情况来考虑：

1. 上一行的格子所在列 c 为下一行的格子所在列 c^ 的左边或正上方，假设 lmax 表示 score(r, c) - (c^-c) 的最大值，则当c^ 从左到右移动的过程中，每向右移动一个格子，对于新的 c^^ 而言，它的 lmax 等于 max(lmax - 1, score(r, c^^))。为什么呢？因为不管上一行选择的格子在左侧的哪一列，对于下一行来说，只要它向右移动一格，它和上一行所选格子在横向上的距离就大了 1，于是有 lmax - 1，而新的 lmax 要么是从原来的 lmax 走下来，要么是从 c^^ 的正上方走下来，后者则不需要扣减分数，于是得出 lmax = max(lmax - 1, score(r, c^^))。
2. 上一行的格子所在列 c 为下一行的格子所在列 c^ 的左边或正上方，这种情况类似，只不过每次下一行都是从右往左移动一个格子。所以，类似的，在这个场景里，我们记从上一行右侧到下一行的最大分数为 rmax。

综合两种情况，我们只要找出 max(lmax, rmax) 的结果即可。

编码实现

每次为新的一行选择格子时，需要参考上一行的选择结果，所以需要空间上需要两个数组：

dp []int64   // 表示上一行每一列求得的最大分数
ndp []int64  // 表示新一行每一列求得的最大分数

最后的代码是：

func max(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func maxPoints(points [][]int) int64 {
    rows := len(points)
    if rows == 0 {
        return 0
    }
    cols := len(points[0])
    dp := make([]int64, cols)

    for r := 0; r < rows; r++ {
        ndp := make([]int64, cols)

        lmax := int64(0)
        for c := 0; c < cols; c++ {
            lmax = max(lmax - 1, dp[c])
            ndp[c] = max(ndp[c], lmax)
        }

        rmax := int64(0)
        for c := cols - 1; c >= 0; c-- {
            rmax = max(rmax - 1, dp[c])
            ndp[c] = max(ndp[c], rmax)
        }

        for c := 0; c < cols; c++ {
            ndp[c] += int64(points[r][c])
        }
        dp = ndp
    }

    ret := int64(0)
    for _, v := range dp {
        if ret < v {
            ret = v
        }
    }
    return ret
}

提交后结果是：

执行用时: 216 ms
内存消耗: 15.3 MB

双100通过。

参考资料

1. Leetcode 第250场周赛讨论区-吴自华的回答

版权声明：本文为原创文章，转载请注明来源：《算法题解：扣分后的最大得分 - Hackerpie》，谢绝未经允许的转载。