1937. Maximum Number of Points with Cost

[mah-shamim]

Topics: Array, Dynamic Programming

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

• x for x >= 0.
• -x for x < 0.

Example 1:

• Input: l1 = [2,4,3], l2 = [5,6,4]
• Output: 9
• Explanation:
  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
• Explanation:
  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

Hint:

1. Try using dynamic programming.
2. dp[i][j] is the maximum number of points you can have if points[i][j] is the most recent cell you picked.

[topugit]

We can break down the solution into several steps:

Step 1: Define the DP Array

We will use a 2D array dp where dp[i][j] represents the maximum points we can achieve by selecting the cell at row i and column j.

Step 2: Initialize the DP Array

Initialize the first row of dp to be the same as the first row of points since there are no previous rows to subtract the cost.

Step 3: Calculate DP Values for Each Row

For each subsequent row, we calculate the maximum possible points for each column considering the costs of switching from the previous row.

To efficiently calculate the transition from row i-1 to row i, we can use two auxiliary arrays left and right:

• left[j] will store the maximum value we can achieve for the j-th column considering only transitions from the left.
• right[j] will store the maximum value we can achieve for the j-th column considering only transitions from the right.

Step 4: Update DP for Each Row

For each column j in row i:

• Update dp[i][j] using the maximum of either left[j] or right[j] plus points[i][j].

Step 5: Return the Maximum Value from the Last Row

The result will be the maximum value in the last row of the dp array.

Let's implement this solution in PHP: 1937. Maximum Number of Points with Cost

<?php
function maxPoints($points) {
    $m = count($points);
    $n = count($points[0]);
    $dp = $points[0];

    for ($i = 1; $i < $m; $i++) {
        // Initialize left and right arrays
        $left = array_fill(0, $n, 0);
        $right = array_fill(0, $n, 0);

        // Calculate the left array
        $left[0] = $dp[0];
        for ($j = 1; $j < $n; $j++) {
            $left[$j] = max($left[$j - 1] - 1, $dp[$j]);
        }

        // Calculate the right array
        $right[$n - 1] = $dp[$n - 1];
        for ($j = $n - 2; $j >= 0; $j--) {
            $right[$j] = max($right[$j + 1] - 1, $dp[$j]);
        }

        // Update dp for the current row
        for ($j = 0; $j < $n; $j++) {
            $dp[$j] = $points[$i][$j] + max($left[$j], $right[$j]);
        }
    }

    return max($dp);
}

// Example usage:
$points1 = [[1, 5], [2, 3], [4, 2]];
$points2 = [[2, 4, 3], [5, 6, 4]];
echo maxPoints($points1); // Output: 11
echo maxPoints($points2); // Output: 9
?>

Explanation:

• left and right arrays: These help us compute the maximum points we can gain for each cell by considering the previous row's values, efficiently accounting for the penalty from moving across columns.
• Dynamic programming approach: This method ensures that each row is calculated based on the previous row, making the solution scalable for large matrices.

This approach has a time complexity of (O(m \times n)), which is efficient given the constraints.

[mah-shamim]

Thanks to solve the 'Maximum Number of Points with Cost' problem using dynamic programming

[topugit]

Thanks