⚡Flashcard Drill➔
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

  1. dp[i][j] is the best score ending at row i, column j.
  2. Naively dp[i][j] = points[i][j] + max over c of (dp[i-1][c] - |j - c|), which is O(m n^2).
  3. Split the absolute value into two sweeps: a left-to-right pass computes max(dp[i-1][c] + c) - j and a right-to-left pass computes max(dp[i-1][c] - c) + j.
  4. 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 / - j bookkeeping: the left pass adds j before subtracting, the right pass subtracts then adds.
  • Seeding best with 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 dp starts as points[0].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems