https://leetcode.com/problems/maximum-number-of-points-with-cost/ from Google

Thinking process:

This is another grid problem. Whenever we are asked about to count numbers in a grid, we use dynamic programming. When using dynamic programming for this kind of problems, we usually have two choices: traversing grid by grid or row by row. You can go to here for a row by row example. In this problem, we’ll solve it grid by grid.

So like I mentioned above, we’ll use DP to solve this. For any given row, we can define dp[i][j] to be the maximum number of points we can achieve at position j in row i. This is exact the same definition of this problem. Usually when handling dp problem, we use the same defintion for each position first, and then use that information to calculate the solutions for other cells.

There are three ways to go to next row: we can move to the same position j, we can move to right, or we can move to left. Let’s assume we can only move from left to right first. So if we know all answers in dp[i-1], then dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-1, dp[i-1][j-2]-2, …) + point[i][j].

With the above formula, we can find all dp[i][j] already. However, the time complexity will be O(C^2*R), which is too big. We need to find another way to make it to be O(C*R).

If we look at the formula carefully, there are some repeat works. For example, to get dp[i][1], we need to get max(dp[i-1][0]-1, dp[i-1][1]). To get dp[i][2], we need to get max(dp[i-1][0]-2, dp[i-1][1]-1, dp[i-1][2]). But, the max(dp[i-1][0]-2, dp[i-1][1]-1) is equal to max(dp[i-1][0]-1, dp[i-1][1]) - 1, which is the answer we calculate in dp[i][1]. So, if we calculate dp[i][1] first, then when calculating dp[i][2], we just need to calculate max(dp[i][1]-1, dp[i-1][2]), which is an O(1) operation.

Likewise, if we go from right to left, we have the same pattern with just opposite direction. Therefore, to calculate the answer for each row of i, we just need to go from left to right and keep calculating max(dp[i][j-1]-1, dp[i-1][j]), and then go from left to right for max(dp[i][j+1], dp[i-1][j]).

Another optization we can do is that, we don’t actually need to allocate memory for all rows. To calculate the answer for ith row, we only need the answer from previous row, so we actually one need two one dimension dp arrays, and another one dimension temp array for calculating answers from left to right and right to left.

After we have a left array and a right array, dp[i] will be equal to max(left[i], right[i]) + points[i]

Below is the code.

 1class Solution {
 2public:
 3    typedef long long ll;
 4    long long maxPoints(vector<vector<int>>& points) {
 5        int M = points.size(), N = points[0].size();
 6        vector<ll> left(N), right(N);
 7        for (int i=0; i<N; i++) {
 8            left[i] = max((ll)points[0][i], i==0?0:(left[i-1]-1));
 9        }
10        for (int i=N-1; i>=0; i--) {
11            right[i] = max((ll)points[0][i], i==N-1?0:(right[i+1]-1));
12        }
13        for (int i=1; i<M; i++) {
14            vector<ll> dp(N);
15            for (int j=0; j<N; j++) {
16                dp[j] = max(left[j], right[j]) + points[i][j];
17            }
18            for (int j=0; j<N; j++) {
19                left[j] = max(dp[j], j==0?0:(left[j-1]-1));
20            }
21            for (int j=N-1; j>=0; j--) {
22                right[j] = max(dp[j], j==N-1?0:(right[j+1]-1));
23            }
24        }
25        ll ans = 0;
26        for (int i=0; i<N; i++) ans = max(ans, max(left[i], right[i]));
27        return ans;
28    }
29};