Leetcode 1937 - Maximum Number of Points with Cost

Link to problem

Problem

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.

Solution

Ignoring the text provided, by taking a look at the example provided on Leetcode, the problem isn’t too hard to understand. And it should be obvious that this question could be solved by dynamic programming (kind of similar to solving knapsack problem).

For an element, the largest point it could achieve is by finding the maximum of:

1. By adding the largest point (with the distant penalty) from left side.
2. By adding the largest point (with the distant penalty) from right side.
3. By adding the point directly above the element.

Therefore, we first do a scan from left to right then right to left. Followed by adding the according points to the dp table.

Implementation

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        size_t n = points.front().size();
        vector<vector<long long>> dp(points.size(), vector<long long>(n));

        for (int i = 0; i < n; i++) {
            dp[0][i] = points[0][i];
        }

        for (int i = 1; i < points.size(); i++) {
            long long temp_max = 0;
            // right side
            for (int j = 0; j < n; j++) {
                temp_max = max(--temp_max, dp[i-1][j]);
                dp[i][j] = temp_max;
            }

            // left
            temp_max = 0;
            for (int j = n-1; j >= 0; j--) {
                temp_max = max(--temp_max, dp[i-1][j]);
                dp[i][j] = max(dp[i][j], temp_max) + points[i][j];
            }
        }

        return *max_element(dp.back().begin(), dp.back().end());
    }
};