NeetCode #715LC-1937Medium2-D Dynamic Programming
← Back to All Problems#715 · #1937 · Maximum Number of Points with Cost(扣分后的最大得分)
📌 Problem Statement & Constraints
Given an
m x n matrix points, choose exactly one cell in each row. The score is the sum of the chosen values minus the total penalty |c1 - c2| over consecutive rows. Return the maximum score. Constraints: 1 <= m, n <= 10^5, 1 <= points[i][j] <= 10^5, and m * n <= 10^5.💡 Core Algorithmic Approaches
dp[i][j]is the best score ending at rowi, columnj.- Naively
dp[i][j] = points[i][j] + max over c of (dp[i-1][c] - |j - c|), which is O(m n^2). - Split the absolute value into two sweeps: a left-to-right pass computes
max(dp[i-1][c] + c) - jand a right-to-left pass computesmax(dp[i-1][c] - c) + j. - Taking the maximum of the two sweeps gives the best predecessor in O(1) per cell.
💻 Benchmark Python3 Implementation
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
m, n = len(points), len(points[0])
dp = points[0][:] # first row has no penalty
for i in range(1, m):
left = [0] * n
best = float("-inf")
for j in range(n):
best = max(best, dp[j] + j) # best predecessor from the left
left[j] = best - j
right = [0] * n
best = float("-inf")
for j in range(n - 1, -1, -1):
best = max(best, dp[j] - j) # best predecessor from the right
right[j] = best + j
dp = [points[i][j] + max(left[j], right[j]) for j in range(n)]
return max(dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): two linear sweeps per row.
💾 Space Complexity
O(n): the current row plus the two sweep arrays.
⚠️ Interview Pitfalls & Follow-ups
- Computing
max(dp[c] - |j - c|)directly: that is O(n) per cell and times out; the two-pass trick removes the absolute value. - Messing up the
+ j/- jbookkeeping: the left pass addsjbefore subtracting, the right pass subtracts then adds. - Seeding
bestwith 0: values are large and positive, so a 0 seed corrupts the maximum; use negative infinity. - Charging the first row a penalty: it has no predecessor, so
dpstarts aspoints[0].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.