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 <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= points[r][c] <= 10^5

解题思路

这是一个典型的动态规划问题。可以用 dp[i][j] 表示选择第 i 行第 j 列时能获得的最大分数。

基本思路： 状态转移方程为：dp[i][j] = points[i][j] + max(dp[i-1][k] - abs(j-k)) 对所有 k

但是朴素的 DP 时间复杂度为 O(m×n²)，对于大数据会超时。

优化思路： 关键观察是 abs(j-k) 可以分解为两种情况：

  • 当 k <= j 时：abs(j-k) = j-k，所以 dp[i-1][k] - abs(j-k) = dp[i-1][k] - j + k
  • 当 k > j 时：abs(j-k) = k-j，所以 dp[i-1][k] - abs(j-k) = dp[i-1][k] + j - k

我们可以预处理两个数组：

  • left[j]：表示从左到右到位置 j 时，dp[i-1][k] + k 的最大值（k <= j）
  • right[j]：表示从右到左到位置 j 时，dp[i-1][k] - k 的最大值（k >= j）

这样每次转移只需要 O(1) 时间，总时间复杂度优化到 O(m×n)。

推荐解法： 使用优化的动态规划，通过预处理消除内层循环。

代码实现

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int m = points.size(), n = points[0].size();
        vector<long long> dp(n);
        
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[j] = points[0][j];
        }
        
        // 处理每一行
        for (int i = 1; i < m; i++) {
            vector<long long> left(n), right(n);
            
            // 计算left数组：从左到右的最大值
            left[0] = dp[0];
            for (int j = 1; j < n; j++) {
                left[j] = max(left[j-1], dp[j] + j);
            }
            
            // 计算right数组：从右到左的最大值
            right[n-1] = dp[n-1] - (n-1);
            for (int j = n-2; j >= 0; j--) {
                right[j] = max(right[j+1], dp[j] - j);
            }
            
            // 更新dp数组
            for (int j = 0; j < n; j++) {
                dp[j] = points[i][j] + max(left[j] - j, right[j] + j);
            }
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        dp = [points[0][j] for j in range(n)]
        
        for i in range(1, m):
            # 计算left数组：从左到右的最大值
            left = [0] * n
            left[0] = dp[0]
            for j in range(1, n):
                left[j] = max(left[j-1], dp[j] + j)
            
            # 计算right数组：从右到左的最大值
            right = [0] * n
            right[n-1] = dp[n-1] - (n-1)
            for j in range(n-2, -1, -1):
                right[j] = max(right[j+1], dp[j] - j)
            
            # 更新dp数组
            for j in range(n):
                dp[j] = points[i][j] + max(left[j] - j, right[j] + j)
        
        return max(dp)

public class Solution {
    public long MaxPoints(int[][] points) {
        int m = points.Length, n = points[0].Length;
        long[] dp = new long[n];
        
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[j] = points[0][j];
        }
        
        // 处理每一行
        for (int i = 1; i < m; i++) {
            long[] left = new long[n];
            long[] right = new long[n];
            
            // 计算left数组：从左到右的最大值
            left[0] = dp[0];
            for (int j = 1; j < n; j++) {
                left[j] = Math.Max(left[j-1], dp[j] + j);
            }
            
            // 计算right数组：从右到左的最大值
            right[n-1] = dp[n-1] - (n-1);
            for (int j = n-2; j >= 0; j--) {
                right[j] = Math.Max(right[j+1], dp[j] - j);
            }
            
            // 更新dp数组
            for (int j = 0; j < n; j++) {
                dp[j] = points[i][j] + Math.Max(left[j] - j, right[j] + j);
            }
        }
        
        long result = dp[0];
        for (int j = 1; j < n; j++) {
            result = Math.Max(result, dp[j]);
        }
        return result;
    }
}

var maxPoints = function(points) {
    const m = points.length, n = points[0].length;
    let dp = new Array(n);
    
    // 初始化第一行
    for (let j = 0; j < n; j++) {
        dp[j] = points[0][j];
    }
    
    // 处理每一行
    for (let i = 1; i < m; i++) {
        const left = new Array(n);
        const right = new Array(n);
        
        // 计算left数组：从左到右的最大值
        left[0] = dp[0];
        for (let j = 1; j < n; j++) {
            left[j] = Math.max(left[j-1], dp[j] + j);
        }
        
        // 计算right数组：从右到左的最大值
        right[n-1] = dp[n-1] - (n-1);
        for (let j = n-2; j >= 0; j--) {
            right[j] = Math.max(right[j+1], dp[j] - j);
        }
        
        // 更新dp数组
        for (let j = 0; j < n; j++) {
            dp[j] = points[i][j] + Math.max(left[j] - j, right[j] + j);
        }
    }
    
    return Math.max(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n)需要遍历每个位置，每个位置的计算通过预处理优化为O(1)
空间复杂度O(n)使用了dp、left、right三个长度为n的数组

相关题目