Maximum Number of Points with Cost

MediumDynamic Programming · Prefix/Suffix Max🧩 Grid DP LeetCode #1937 ↗Updated Oct 30, 2026

Problem

You are given an m x n matrix points of non-negative scores. Pick exactly one cell in every row and add up their values. However, for each pair of consecutive rows, if you picked column c1 above and c2 below, you lose |c1 - c2| points. Return the maximum total you can end with.

Input[[1,2,3],[1,5,1],[3,1,1]]Output9 (3 + 5 + 3 - 1 - 1)

Input[[1,5],[2,3],[4,2]]Output11 (5 + 3 + 4 - 0 - 1)

1 ≤ m, n ≤ 10⁵ · m · n ≤ 10⁵ · 0 ≤ points[r][c] ≤ 10⁵ · totals can exceed int ⇒ return long

Try it yourself

Java

class Solution {
    public long maxPoints(int[][] points) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The transition max_p(prev[p] - |p - c|) splits into two halves: p ≤ c and p ≥ c. A left-to-right sweep (decaying by 1 per step) and a right-to-left sweep compute both halves for every column in O(n).

PatternGrid DP

Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.

Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.

Open the Grid DP guide →

Approaches

Brute ForceRecursion over Column Choices

Time O(n^m)Space O(m)

Choose a column in the current row, then recursively try every column in the next row, paying the distance penalty. Every combination of one column per row is examined, which is the definition of the answer.

Java

public long maxPoints(int[][] points) {
    long best = Long.MIN_VALUE;
    for (int c = 0; c < points[0].length; c++) best = Math.max(best, bestFrom(points, 0, c));
    return best;
}

// Best total for rows r..m-1 given that column c is picked in row r
private long bestFrom(int[][] points, int r, int c) {
    long here = points[r][c];
    if (r == points.length - 1) return here;
    long bestNext = Long.MIN_VALUE;
    for (int next = 0; next < points[0].length; next++) {
        bestNext = Math.max(bestNext, bestFrom(points, r + 1, next) - Math.abs(c - next));
    }
    return here + bestNext;
}

Obviously correct, but explodes as soon as there are a few rows.

BetterRow-by-Row DP (All Pairs)

Time O(m · n²)Space O(n)

The best total ending at (r, c) only depends on the best totals of row r-1. Keep prev[] and, for each column, scan every previous column to find max(prev[p] - |p - c|).

Java

public long maxPoints(int[][] points) {
    int m = points.length, n = points[0].length;
    long[] prev = new long[n];
    for (int c = 0; c < n; c++) prev[c] = points[0][c];
    for (int r = 1; r < m; r++) {
        long[] cur = new long[n];
        for (int c = 0; c < n; c++) {
            long best = Long.MIN_VALUE;
            for (int p = 0; p < n; p++) best = Math.max(best, prev[p] - Math.abs(p - c));
            cur[c] = best + points[r][c];
        }
        prev = cur;
    }
    long ans = Long.MIN_VALUE;
    for (long v : prev) ans = Math.max(ans, v);
    return ans;
}

Removes the exponential blow-up, but n² per row is too slow for one wide row.

OptimalLeft & Right Running Max

Time O(m · n)Space O(n)

left[c] = max(left[c-1] - 1, prev[c]) is the best prev[p] - (c - p) over p ≤ c: moving one column further costs exactly one more point. right[c] is the mirror image, and the transition is points[r][c] + max(left[c], right[c]).

Java

public long maxPoints(int[][] points) {
    int m = points.length, n = points[0].length;
    long[] prev = new long[n];
    for (int c = 0; c < n; c++) prev[c] = points[0][c];
    long[] left = new long[n], right = new long[n];
    for (int r = 1; r < m; r++) {
        left[0] = prev[0];
        for (int c = 1; c < n; c++) left[c] = Math.max(left[c - 1] - 1, prev[c]);
        right[n - 1] = prev[n - 1];
        for (int c = n - 2; c >= 0; c--) right[c] = Math.max(right[c + 1] - 1, prev[c]);
        long[] cur = new long[n];
        for (int c = 0; c < n; c++) cur[c] = points[r][c] + Math.max(left[c], right[c]);
        prev = cur;
    }
    long ans = Long.MIN_VALUE;
    for (long v : prev) ans = Math.max(ans, v);
    return ans;
}

Dry run[[1,2,3],[1,5,1],[3,1,1]]

* best column changed

row 0
1

2

3

prev = first row
left
1

2

3

carry best from left, -1
right
1

2

3

carry best from right, -1
row 1
2

7
*
4

[1,5,1] + max(left,right)
max l/r
6

7

6

7 decays by 1 each side
row 2
9
*
8

7

3 + 6 = 9 ✔

Linear in the matrix size — handles both very tall and very wide inputs.

Pro tip

Say it out loud: “moving one column further away costs exactly 1, so the best candidate from the left can be carried forward with a -1 per step.”

At a glance

Level	Approach	Time	Space
Brute Force	Recursion over Column Choices	`O(n^m)`	`O(m)`
Better	Row-by-Row DP (All Pairs)	`O(m · n²)`	`O(n)`
Optimal	Left & Right Running Max	`O(m · n)`	`O(n)`

Common pitfalls

Returning int — 10⁵ rows of 10⁵ points overflow; use long.
Taking only the left sweep — the best previous column can be to the right.
Picking the row maximum greedily — the penalty can make a smaller nearby cell better.

Interview tips

Write the O(m·n²) DP first, then ask how to speed up the inner max.
Split |p - c| into the two cases p ≤ c and p ≥ c on the whiteboard.
Note the constraint m·n ≤ 10⁵: a single row can be 10⁵ wide.

Pattern

DP with |i - j| transition cost → replace the inner max loop with a forward and a backward running max.

My notes saved in this browser