LeetCode每日一题(1937. Maximum Number of Points with Cost)

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

x for x >= 0.
-x for x < 0.

Example 1:

Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9

Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.

Example 2:

Input: points = [[1,5],[2,3],[4,2]]
Output: 11

Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.

Constraints:

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

---

这题还是挺有意思的，有篇此题的解法写的很好(https://leetcode.com/problems/maximum-number-of-points-with-cost/discuss/1344908/C%2B%2BJavaPython-3-DP-Explanation-with-pictures-O(MN)-Time-O(N)-Space), 建议大家去看一下。

说一下我的思路:

假设 dp[row-1][col]是我在选择 points[row][col]时所能拿到的前 row+1 行的最大分数, 则可以推出 dp[row][col] = points[row][col] + dp[row-1][col], 但是此时的 dp[row][col]只是相对于我们拿取 points[row][col]的最大分数， 如果我们把视角放到 dp[row]这一行来看，对应 col 的最大值不一定就是 dp[row][col], 所以我们需要横向对比一次，确定对应每个 col 的最大值，这里我们需要从左到右和从右到左两次对比， 简单来说从左到右是 dp[row][col] = max(dp[row][col-1]-1, dp[row][col]), 从右到左是 dp[row][col] = max(dp[row][col+1]-1, dp[row][col]), 之所以是 dp[row][col-1]-1 和 dp[row][col+1]-1 是因为我们每次都是拿取加上横向位移惩罚之后的值。然后此时的 dp[row][col]的实际意义变为， 当我选择 points[row+1][col]时所能拿到的前 row+1 行的最大值

---

impl Solution {
    pub fn max_points(points: Vec<Vec<i32>>) -> i64 {
        let mut dp = vec![vec![0i64; points[0].len()]; points.len() + 1];
        for row in 1..points.len() + 1 {
            for col in 0..points[0].len() {
                dp[row][col] = points[row - 1][col] as i64 + dp[row - 1][col];
            }
            for col in 1..points[0].len() {
                dp[row][col] = dp[row][col].max(dp[row][col - 1] - 1);
            }
            for col in (0..points[0].len() - 1).rev() {
                dp[row][col] = dp[row][col].max(dp[row][col + 1] - 1);
            }
        }
        dp.last().unwrap().into_iter().map(|v| *v).max().unwrap()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17