What is the main pattern in Maximum Number of Points with Cost?

The main pattern is state transition dynamic programming, computing the maximum score per column while considering previous row selections and distance penalties.

How do I handle distance costs efficiently?

Use left-to-right and right-to-left sweeps on the DP array for each row to efficiently account for abs(c1 - c2) without nested loops.

Can I reduce memory usage for this problem?

Yes, by reusing a single DP array for each row instead of a full m x n table, you achieve O(n) space complexity.

Why do we need two passes per row?

Left-to-right and right-to-left passes ensure that each column accounts for the maximum reachable value from previous row considering distance penalties.

What is the time complexity for Maximum Number of Points with Cost?

The time complexity is O(m * n) because each cell in every row is processed once with efficient state transitions.

#1937

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

扣分后的最大得分

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。你的得分方式为：每一行中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分增加 points[r][c] 。然而，相邻行之间被选中的格子如果隔得太远，你会失…

数组动态规划矩阵

题目描述

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c₁) 和 (r + 1, c₂) 的格子，你的总得分减少 abs(c₁ - c₂) 。

请你返回你能得到的最大得分。

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示选取前 $i-1$ 行，并且第 $i-1$ 行选择第 $j$ 列的格子时的最大得分。初始时 $f[0][j] = points[0][j]$ 。

对于 $i > 0$ 的情况，对于 $f[i][j]$ ，我们考虑是从上一行的哪一列转移过来的，记上一行选择的列为 $k$ ，那么有：

f[i][j]= \begin{cases} \max(f[i - 1][k] + k - j + points[i][j]), & 0 \le k < j \\ \max(f[i - 1][k] - k + j + points[i][j]), & j < k < n \end{cases}

其中 $n$ 表示列数。答案为 $\max\limits_{0 \le j < n} f[m - 1][j]$ 。

我们注意到 $f[i]$ 的值只跟 $f[i-1]$ 的值有关，因此我们可以使用滚动数组优化空间复杂度。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points[0])
        f = points[0][:]
        for p in points[1:]:
            g = [0] * n
            lmx = -inf
            for j in range(n):
                lmx = max(lmx, f[j] + j)
                g[j] = max(g[j], p[j] + lmx - j)
            rmx = -inf
            for j in range(n - 1, -1, -1):
                rmx = max(rmx, f[j] - j)
                g[j] = max(g[j], p[j] + rmx + j)
            f = g
        return max(f)

speed

复杂度分析

指标	值
时间	complexity is O(m * n) because each row is processed in linear time with respect to columns. Space complexity is O(n) since only a single row's DP values are stored and updated, avoiding a full m x n matrix.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Focus on dynamic programming state transitions across rows.
question_mark
Check for off-by-one errors in distance subtraction.
question_mark
Ask about optimizing space from O(m*n) to O(n).

warning

常见陷阱

外企场景

error
Forgetting to subtract distance cost correctly between rows.
error
Using full m x n DP unnecessarily, causing memory issues.
error
Confusing left-to-right and right-to-left sweeps when optimizing the update.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute maximum points when distance cost uses squared difference instead of absolute.
arrow_right_alt
Find maximum points if skipping some rows is allowed with no penalties.
arrow_right_alt
Calculate maximum points in a triangular or irregular shaped matrix with the same distance rules.

help

常见问题

外企场景

继续练习

#1981 最小化目标值与所选元素的差 #2088 统计农场中肥沃金字塔的数目 #1728 猫和老鼠 II