#1937

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number of Points with Cost

Maximize your points in a matrix by selecting cells row by row while accounting for distance penalties using dynamic programming.

array dynamic programming matrix

Problem Statement

You are given an m x n integer matrix points. Starting with zero points, select exactly one cell from each row. Picking cell (r, c) adds points[r][c] to your total, but each choice affects the next row.

For every two adjacent rows r and r + 1, selecting cells (r, c1) and (r + 1, c2) subtracts abs(c1 - c2) from your total. Compute the maximum total points obtainable by carefully choosing one cell per row while minimizing the cost from column distance.

Examples

Example 1

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

Output: 9

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

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

Solution Approach

Dynamic Programming Table

Create a DP array where dp[c] stores the maximum score ending at column c in the current row. Initialize it with the first row values since there is no previous row.

Row-wise State Transition

For each subsequent row, compute the maximum achievable points for each column by considering the previous row's dp values minus the distance cost. Use left-to-right and right-to-left sweeps to efficiently calculate max(dp[c] - abs(c - k)) for all columns k.

Space Optimization

Instead of a full m x n DP table, reuse a single array of size n. Update it in-place for each row using temporary arrays for left and right passes, reducing memory while keeping the state transitions intact.

Complexity Analysis

Metric	Value
Time	O(m \cdot n)
Space	O(n)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Continue Practicing

#1981 minimize the difference between target and chosen elements #2088 count fertile pyramids in a land #1728 cat and mouse ii