扣分后的最大得分

标签: 数组 动态规划

难度: Medium

给你一个 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：

输入：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 。

示例 2：

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

 

提示：

  • m == points.length
  • n == points[r].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 0 <= points[r][c] <= 105

Submission

运行时间: 440 ms

内存: 38.9 MB

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        r, c = len(points), len(points[0])
        dp1, dp2 = points[0], [0] * c
        for p in points[1:]:
            left, right = [0] * c, [c - 1] * c  # 左右的最大值
            mx_i = 0
            for i in range(1, c):
                if dp1[mx_i] - (i - mx_i) < dp1[i - 1] - 1:
                    mx_i = i - 1
                left[i] = mx_i  # p[i] 左侧能产生最大值的下标
            mx_i = c - 1
            for i in range(c - 2, -1, -1):
                if dp1[mx_i] - (mx_i - i) < dp1[i + 1] - 1:
                    mx_i = i + 1
                right[i] = mx_i
            for i in range(c):
                l, r = left[i], right[i]
                dp2[i] = max(dp1[l] - (i - l), dp1[r] - (r - i), dp1[i]) + p[i]
            dp1, dp2 = dp2, [0] * c
        return max(dp1)

Explain

此题解采用了动态规划的方法。首先，定义dp1数组来存储上一行在选择某一列时可以获得的最大得分。对于每一行，使用一个新的dp2数组来计算当前行选择每一列的最大可能得分。为了有效处理列间的距离扣分问题，引入两个辅助数组left和right，它们分别记录从左到右和从右到左遍历时可以获取的最大得分下标。通过这种方式，可以在O(1)的时间内确定任何一个位置选择后，从上一行得到的最大贡献值。最后通过迭代更新dp1数组，使得每行计算完后，dp1都存储了当前行的最优解。这个过程重复直到最后一行，最后在dp1中找到最大值，即为最大得分。

时间复杂度: O(mn)

空间复杂度: O(n)

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        r, c = len(points), len(points[0])
        dp1, dp2 = points[0], [0] * c  # 初始化第一行的得分和下一行的得分存储
        for p in points[1:]:
            left, right = [0] * c, [c - 1] * c  # 从左和从右计算每列的最大得分下标
            mx_i = 0
            for i in range(1, c):  # 从左向右填充最优下标
                if dp1[mx_i] - (i - mx_i) < dp1[i - 1] - 1:
                    mx_i = i - 1
                left[i] = mx_i
            mx_i = c - 1
            for i in range(c - 2, -1, -1):  # 从右向左填充最优下标
                if dp1[mx_i] - (mx_i - i) < dp1[i + 1] - 1:
                    mx_i = i + 1
                right[i] = mx_i
            for i in range(c):  # 计算当前行每一列的最大得分
                l, r = left[i], right[i]
                dp2[i] = max(dp1[l] - (i - l), dp1[r] - (r - i), dp1[i]) + p[i]
            dp1, dp2 = dp2, [0] * c  # 更新dp1为当前行的最优解，重置dp2
        return max(dp1)  # 返回最大得分

Explore

在动态规划解法中，dp1数组是以输入矩阵的第一行即points[0]来初始化的。这种初始化方式利用了第一行的分数直接作为起始最大分数的基准。这种初始化方式适用于所有情况，因为对于每一个问题实例，第一行总是存在的，且每个位置都有一个初始分数值。初始化dp1为第一行的得分确保了动态规划在开始迭代之前有一个有效的起始状态。

在计算left和right数组时，特别考虑更新最优下标是为了快速找到从上一行转移到当前行时避免较大扣分的最佳位置。题目中由于列之间的选择会根据距离产生扣分，因此需要找到一个折中点，使得即使有扣分，也能获得较高的上一行得分。left数组从左向右计算，记录能得到最大得分的列下标；right数组从右向左计算，同样记录能得到最大得分的列下标。这种策略直接与题目的需求关联，因为它允许我们在保持得分最大化的同时，计算每一列选择后的最优得分，从而处理列间距离的扣分问题。

是的，使用的贪心策略确保了每一列都能得到可能的最大得分。这种策略通过分别从左到右和从右到左填充left和right数组，确保了无论从哪个方向考虑，都能找到一个在考虑列间距离扣分后仍然保持最大得分的上一行的列。在计算当前行每个位置的得分时，通过比较这两个方向的最大得分（调整后的），以及不移动直接从上一行同列继承得分，从三者中选择最大值，确保了每一列的得分都是最大可能得分。

这种方法确保总得分最大化的关键在于它允许每一列在选择时考虑到从上一行任何可能的列转移来的得分，同时计算这种转移带来的扣分（列索引差的绝对值）。通过比较所有可能的来源列（即通过left和right数组确定的两个最佳来源列以及当前列本身），选择一个得分最高的选项。这样，每一步都在尽可能地选择最优解，通过这种局部最优选择来逼近全局最优，从而在整个矩阵遍历完成后，能够确保获得可能的最大得分。