扣分后的最大得分
难度:
标签:
题目描述
给你一个 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.lengthn == points[r].length1 <= m, n <= 1051 <= m * n <= 1050 <= points[r][c] <= 105
代码结果
运行时间: 440 ms, 内存: 38.9 MB
/*
* 题目思路：
* 1. 使用Java Stream处理数据，简化代码结构。
* 2. 通过Stream计算每行最大得分和邻行最大得分之间的差异。
* 3. 逐行计算累加最大得分，处理扣分逻辑。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
int[] prevRow = IntStream.of(points[0]).toArray();
for (int i = 1; i < m; i++) {
int[] maxLeft = new int[n];
int[] maxRight = new int[n];
int[] currentRow = new int[n];
maxLeft[0] = prevRow[0];
for (int j = 1; j < n; j++) {
maxLeft[j] = Math.max(maxLeft[j - 1], prevRow[j] + j);
}
maxRight[n - 1] = prevRow[n - 1] - (n - 1);
for (int j = n - 2; j >= 0; j--) {
maxRight[j] = Math.max(maxRight[j + 1], prevRow[j] - j);
}
for (int j = 0; j < n; j++) {
currentRow[j] = points[i][j] + Math.max(maxLeft[j] - j, maxRight[j] + j);
}
prevRow = currentRow;
}
return IntStream.of(prevRow).max().orElse(0);
}
}
解释
方法:
此题解采用了动态规划的方法。首先，定义dp1数组来存储上一行在选择某一列时可以获得的最大得分。对于每一行，使用一个新的dp2数组来计算当前行选择每一列的最大可能得分。为了有效处理列间的距离扣分问题，引入两个辅助数组left和right，它们分别记录从左到右和从右到左遍历时可以获取的最大得分下标。通过这种方式，可以在O(1)的时间内确定任何一个位置选择后，从上一行得到的最大贡献值。最后通过迭代更新dp1数组，使得每行计算完后，dp1都存储了当前行的最优解。这个过程重复直到最后一行，最后在dp1中找到最大值，即为最大得分。
时间复杂度:
O(mn)
空间复杂度:
O(n)
代码细节讲解
🦆
在动态规划解法中，是如何初始化dp1数组的，以及这种初始化方式是否适用于所有情况？
▷🦆
为什么在计算left和right数组时，需要特别考虑更新最优下标？这种更新策略与题目的需求有什么直接关系？
▷🦆
在处理两个辅助数组left和right时，使用的贪心策略是否确保了每一列都能得到可能的最大得分？
▷🦆
解法中提到，dp2每一列的值是基于dp1的特定列减去列索引差的绝对值再加上当前值计算得出，这种方法如何确保总得分最大化？
▷