1937

1937. Maximum Number of Points with Cost (Medium)

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: points = [[1,2,3],[1,5,1],[3,1,1]]
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

Similar Questions:

• Minimum Path Sum (Medium)

Solution 1. DP

Let dp[i+1][j] be the maximum point we can get with first i rows if we selected A[i+1][j] in the ith row.

For the 0th row:

dp[0][j] = A[0][j]

For the ith row (i >= 1):

dp[i+1][j] = max( dp[i][t] + A[i+1][j] - abs(t - j) | 0 <= t < N )
         = A[i+1][j] + max( dp[i][t] - abs(t - j) | 0 <= t < N )
         = max(
                A[i+1][j] + max( dp[i][t] - j + t | 0 <= t < j ),
                A[i+1][j] + max( dp[i][t] - t + j | j <= t < N )
              )
         = max(
                A[i+1][j] - j + max( dp[i][t] + t | 0 <= t < j ),
                A[i+1][j] + j + max( dp[i][t] - t | j <= t < N )
              )

This means that for a given dp[i+1][j], we need to compute:

• max( dp[i][t] + t | 0 <= t < j )
• max( dp[i][t] - t | j <= t < N )

So we can do it in two pass:

1. First pass, from left to right. dp[i+1][j] = A[i+1][j] - j + mx where mx = max( dp[i][t] + t | 0 <= t <= j )
2. Second pass, from right to left. dp[i+1][j] = max( dp[i+1][j], A[i+1][j] + j + mx) where mx = max( dp[i][t] - t | j <= t < N ).

Since dp[i+1][j] is only dependent on the values in the previous row, we can reduce space of dp from M * N to 1 * N.

The result is max( dp[N - 1][j] | 0 <= j < N ).

// OJ: https://leetcode.com/problems/maximum-number-of-points-with-cost/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    long long maxPoints(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<long long> dp(N);
        for (int i = 0; i < N; ++i) dp[i] = A[0][i];
        for (int i = 1; i < M; ++i) {
            vector<long long> next(N);
            long long mx = dp[0];
            for (int j = 0; j < N; ++j) {
                mx = max(mx, dp[j] + j);
                next[j] = A[i][j] - j + mx;
            }
            mx = dp[N - 1] - (N - 1);
            for (int j = N - 1; j >= 0; --j) {
                mx = max(mx, dp[j] - j);
                next[j] = max(next[j], A[i][j] + j + mx);
            }
            swap(next, dp);
        }
        return *max_element(begin(dp), end(dp));
    }
};