Problem Description

You are given a 2D array points with m rows and n columns, where points[i][j] represents the number of points you can earn at cell (i, j).

You must pick one cell from each row, starting from the first row to the last. The total score you earn is the sum of the values of all chosen cells, but with a penalty: if you pick cell (i, j) and then cell (i+1, k) in the next row, you pay a cost of abs(j - k) (the absolute difference of their column indices).

Your goal is to maximize your total score by choosing one cell from each row, accounting for the penalty at each step.

Constraints:

• Each row, you must pick exactly one cell.
• You cannot skip rows or pick more than one cell per row.
• The penalty applies between every pair of consecutive rows.

    Input: points = [[1,2,3],[1,5,1],[3,1,1]]
    Output: 9
    Explanation: Pick cells (0,2) -> (1,1) -> (2,0): 3 + 5 + 3 = 11, penalties are |2-1|=1 and |1-0|=1, so total = 11 - 2 = 9.
    

Thought Process

The first instinct might be to try all possible paths: for each row, try every possible cell and keep track of the total score and penalty. However, this brute-force approach quickly becomes infeasible due to the exponential number of possible paths as the matrix grows.

Recognizing that each choice in a row only depends on the choices made in the previous row, we can think in terms of dynamic programming. At each step, we want to know, for each cell in the current row, the best score we can achieve if we end up at that cell, considering all possible ways to get there from the previous row.

The main challenge is efficiently handling the penalty, which depends on the distance between columns in consecutive rows. Naively, for each cell, we could check every cell in the previous row, but this leads to an O(m*n*n) solution, which can be too slow. The key is to optimize this transition using clever observations about the penalty structure.

Solution Approach

We use dynamic programming to solve this problem efficiently. Here's a step-by-step breakdown:

1. Define DP State: Let dp[i][j] be the maximum score we can get by picking cell (i, j) on row i.
2. Base Case: For the first row, dp[0][j] = points[0][j] for all columns j.
3. Transition: For each cell (i, j) in row i, we want to compute:
   dp[i][j] = max(dp[i-1][k] - abs(j - k)) + points[i][j] for all k in previous row.
   This is O(n^2) per row, but we can optimize it:
   • Optimization: For each row, perform two passes:
     • Left-to-Right: For each j, keep track of the maximum value of dp[i-1][k] + k seen so far, and subtract j (since -abs(j-k) = k-j when k <= j).
     • Right-to-Left: For each j, keep track of the maximum value of dp[i-1][k] - k seen so far, and add j (since -abs(j-k) = j-k when k >= j).
     For each cell, take the maximum from both passes.
4. Result: The answer is the maximum value in the last row of dp.

Example Walkthrough

Let's use the sample input: points = [[1,2,3],[1,5,1],[3,1,1]]

Step 1: Initialize DP for row 0

• dp[0] = [1, 2, 3]

• For cell (1,0):
  max(dp[0][k] - abs(0-k)) = max(1-0, 2-1, 3-2) = max(1,1,1) = 1
  dp[1][0] = 1 (from above) + 1 (points[1][0]) = 2
• For cell (1,1):
  max(1-1, 2-0, 3-1) = max(0,2,2) = 2
  dp[1][1] = 2 + 5 = 7
• For cell (1,2):
  max(1-2, 2-1, 3-0) = max(-1,1,3) = 3
  dp[1][2] = 3 + 1 = 4
• So dp[1] = [2, 7, 4]

• For cell (2,0):
  max(2-0, 7-1, 4-2) = max(2,6,2) = 6
  dp[2][0] = 6 + 3 = 9
• For cell (2,1):
  max(2-1, 7-0, 4-1) = max(1,7,3) = 7
  dp[2][1] = 7 + 1 = 8
• For cell (2,2):
  max(2-2, 7-1, 4-0) = max(0,6,4) = 6
  dp[2][2] = 6 + 1 = 7
• So dp[2] = [9, 8, 7]

Time and Space Complexity

Brute-force Approach:

• For each row, try every possible cell in every previous row: O(n^m), which is infeasible for large inputs.

• For each cell, loop over all cells in the previous row: O(m * n^2).

• For each row, do two linear passes (left-to-right and right-to-left): O(m * n).
• Space: O(n) if we only keep the previous and current row, or O(m * n) if we keep the full DP table.

Summary

The problem asks us to maximize the total points earned by picking one cell per row in a grid, paying a penalty for switching columns between rows. By recognizing the structure of the penalties, we can use dynamic programming and optimize the state transitions with two linear passes per row. This reduces what could be an exponential or quadratic problem to a linear one in terms of the number of cells, making it both elegant and efficient.

Code Implementation

class Solution:
    def maxPoints(self, points):
        m, n = len(points), len(points[0])
        dp = points[0][:]
        for i in range(1, m):
            left = [0] * n
            right = [0] * n
            left[0] = dp[0]
            for j in range(1, n):
                left[j] = max(left[j-1]-1, dp[j])
            right[-1] = dp[-1]
            for j in range(n-2, -1, -1):
                right[j] = max(right[j+1]-1, dp[j])
            for j in range(n):
                dp[j] = points[i][j] + max(left[j], right[j])
        return max(dp)
      

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int m = points.size(), n = points[0].size();
        vector<long long> dp(points[0].begin(), points[0].end());
        for (int i = 1; i < m; ++i) {
            vector<long long> left(n), right(n);
            left[0] = dp[0];
            for (int j = 1; j < n; ++j)
                left[j] = max(left[j-1] - 1, dp[j]);
            right[n-1] = dp[n-1];
            for (int j = n-2; j >= 0; --j)
                right[j] = max(right[j+1] - 1, dp[j]);
            for (int j = 0; j < n; ++j)
                dp[j] = points[i][j] + max(left[j], right[j]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};
      

class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length, n = points[0].length;
        long[] dp = new long[n];
        for (int j = 0; j < n; j++) dp[j] = points[0][j];
        for (int i = 1; i < m; i++) {
            long[] left = new long[n], right = new long[n];
            left[0] = dp[0];
            for (int j = 1; j < n; j++)
                left[j] = Math.max(left[j-1] - 1, dp[j]);
            right[n-1] = dp[n-1];
            for (int j = n-2; j >= 0; j--)
                right[j] = Math.max(right[j+1] - 1, dp[j]);
            for (int j = 0; j < n; j++)
                dp[j] = points[i][j] + Math.max(left[j], right[j]);
        }
        long ans = 0;
        for (long v : dp) ans = Math.max(ans, v);
        return ans;
    }
}
      

var maxPoints = function(points) {
    const m = points.length, n = points[0].length;
    let dp = points[0].slice();
    for (let i = 1; i < m; i++) {
        let left = Array(n), right = Array(n);
        left[0] = dp[0];
        for (let j = 1; j < n; j++)
            left[j] = Math.max(left[j-1] - 1, dp[j]);
        right[n-1] = dp[n-1];
        for (let j = n-2; j >= 0; j--)
            right[j] = Math.max(right[j+1] - 1, dp[j]);
        for (let j = 0; j < n; j++)
            dp[j] = points[i][j] + Math.max(left[j], right[j]);
    }
    return Math.max(...dp);
};