# 1937. Maximum Number of Points with Cost

## Latest:

[https://www.youtube.com/watch?v=ik1y7fz8AOc](https://www.youtube.com/watch?v=ik1y7fz8AOc)

```java
class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[] prevRow = new long[n];
        long[] curRow = new long[n];
        
        for (int j = 0; j < n; j++) { // for big number add...use long
            prevRow[j] = points[0][j];
        }
        long result = 0;

        for (int i = 1; i < m; i++) {
            long[] leftMax = new long[n];
            long[] rightMax = new long[n];

            leftMax[0] = prevRow[0];
            for (int j = 1; j < n; j++) {
                leftMax[j] = Math.max(leftMax[j-1] - 1, prevRow[j]);
            }

            rightMax[n-1] = prevRow[n-1];
            for (int j = n-2; j >= 0; j--) {
                rightMax[j] = Math.max(rightMax[j+1] - 1, prevRow[j]);
            }
            for (int j = 0; j < n; j++) {
                curRow[j] = points[i][j];
                curRow[j] += Math.max(leftMax[j], rightMax[j]);
            }
            prevRow = curRow;
        }

        for (int j = 0; j < n; j++) {
            result = Math.max(result, prevRow[j]); // for only one row case, if it's one row, then ans is in prevRow
        }
        return result;
    }
}
/**

cal left max array
   right max  
if m = 3, left start from 1 , right start from m-2
 left max = left[1] = max(left[1-1] - 1, prev_row[1])  
 right max = right[1] = max(right[3-2] - 1, prev_row[1]) 
so we can have left max and right max
curr_row[1] = curr_row[1] + max(left_max[1], right_max[1])
continuously cal to last row, then ans is the max(last_row)

          1 2 3
left max for 5          ->.  5 + max(1a - 1, 2) = 7
          1a 5 1c
right max for 5.        ->  5 + max(1c -1, 2) =  7

      1. 2 3
left. 1. 2 3
right 1  2 3
      1  5.1 ->  1 + max(1, 1), 5 + max(2, 2), 1 + max(3, 3) = 
      2  7 4 

so 1 5 1 to
          2 7 4
left      2 7 6          
right     6 7 4 
          3 1 1.   3 + max(left[0], right[0]) = 3 + max(2, 6) = 9

          9 8 7.  ->.  max(last row) = 9

so this way is 
T: O(mn), m is row, n is col, for each row, cal left_max (n), and right_max(n) -> m*(2n)
S: O(n), left_max, right_max array          
 */


```



like 931, 但分支太多, 所以 dfs + memo 會不過 (931 只有 3個分支, 這題有 n 個分支（n is num of col)

## DFS + memo (Time Limit Exceeded

T: O(col^row)

S: O(row\*col)

```java
class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        
        Long[][] memo = new Long[m][n];
        long max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) { // each cell in row 0
            max = Math.max(max, dfs(points, 0, i, memo));
        }
        return max;
    }
    private long dfs(int[][] points, int row, int col, Long[][] memo) {
        int m = points.length;
        int n = points[0].length;
        
        if(row == m - 1) {
            return points[row][col];
        }
        
        if (memo[row][col] != null) {
            return memo[row][col];
        }
        
        long max = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // notice, in dfs, run (row+1, all cols)            
            long sum = points[row][col] + dfs(points, row+1, i, memo) - Math.abs(col - i);
            max = Math.max(max, sum);
        }
        memo[row][col] = max;
        return max;
    }

}

/*
row 0, col 0~3

p(0,0)
+
(r+1, col i 0~3) - abs|i - col|


[
[1,2,3],
[1,5,1], 7
[3,1,1]]


[
[1,5],
[2,3],
[4,2]]

*/
```

## DP

```java
class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[][] dp = new long[m][n];
        
        
        for (int j = 0; j < n; j++) { 
            dp[0][j] = points[0][j]; // first row value
        }
        
        for (int i = 1; i < m; i++) {
            long rollingMax = Long.MIN_VALUE; // 每次 row 都會拿到一個最大值, 所以要宣告在這
            for (int j = 0; j < n; j++) {
                // System.out.println("i:"+i);
                // System.out.println("dp[i-1][j]:"+dp[i-1][j]+",j:"+ j);
                // System.out.println("dp[i-1][j] + j:"+ (dp[i-1][j] + j)+"\n");
                
                rollingMax = Math.max(rollingMax, dp[i-1][j] + j);
                // System.out.println("rollingMax:" + rollingMax);
                dp[i][j] = Math.max(dp[i][j], (points[i][j] - j) +  rollingMax);

            }
            rollingMax = Long.MIN_VALUE;
            for (int j = n-1; j >= 0; j--) { // why reverse?
                // System.out.println("i:"+i);
                // System.out.println("dp[i-1][j]:"+dp[i-1][j]+",j:"+ j);
                // System.out.println("dp[i-1][j] - j:"+ (dp[i-1][j] - j)+"\n");
                rollingMax = Math.max(rollingMax, dp[i-1][j] - j);
                // System.out.println("rollingMax:" + rollingMax);
                dp[i][j] = Math.max(dp[i][j], (points[i][j] + j) +  rollingMax);
            }
        }
        /*[
        [1,5],
        [2,3],
        [4,2]]
        */

        long res = Long.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            res = Math.max(res, dp[m-1][j]);
        }
        return res;
    }
}

/*
sol 1.
for (int i = 0 ~m)
    for (int j = 0~n)
      for(int k = 0 ~n)
            dp[i][j] = Max(points[i][j] + dp[i-1][k] + abs(j-k))

T: O(m*n*n), => TLE, m, n is 10^5, too big


sol 2.
T: O(m*n)

dp[i][j] = from row 0~m-1, points[i][j] which is the maximum points you can obtain

dp[i][j] = Max(points[i][j] + dp[i-1][k] + abs(j-k)) => 

when j-k >= 0
dp[i][j] = (points[i][j] + j) + max(dp[i-1][k] -k), k= 0, 1, ...~j (從0 開始滾)

dp[i][0] = (points[i][0] + 0) + max(dp[i-1][0] -0)
dp[i][1] = (points[i][1] + 1) + max(dp[i-1][0] -0, dp[i-1][1] -1)
dp[i][2] = (points[i][2] + 2) + max(dp[i-1][0] -0, dp[i-1][1] -1, dp[i-1][2] -2 )...

=>

for (int i = 1 ~m)
    for (int j = 0~n)
        int rollingMax = Math.max(rollingMax, dp[i-1][j] +j);
        dp[i][j] = Math.max(dp[i][j], (points[i][j] - j) +  rollingMax);

when j-k <= 0, 就反過來
dp[i][j] = (points[i][j] - j) + max(dp[i-1][k] + k), k= j, j+1, ...~n-1 (從 n-1 開始滾)

為什麼. for k>=j 時
for (int j=n-1; j>=0; j--)
{
    rollingMax = max(rollingMax, dp[i-1][j]-j);
    dp[i][j] = max(dp[i][j], rollingMax +points[i][j] + j);
}
一定要從 n-1 後面 rolling 過來呢

因為這裡是 -k, 所以從後面大的開始滾, max 的值會從小到大滾出來



for (int i = 1 ~m)
    for (int j = 0~n)=> 這不行, 要到序
        int rollingMax = Math.max(rollingMax, dp[i-1][j] - j);
        dp[i][j] = Math.max(dp[i][j], (points[i][j] + j) +  rollingMax);
*/
```



another explain

```
/*
for i
 for j
    for (k = 0~n) {
    dp[i][j] = max(dp[i-1][k] - abs(j - k)) + A[i][j]
 }
 
how to reduce for (k = 0~n), this part?

abs(j-k) => can be two cases

 1. j - k >= 0 => - abs(j - k) => -(j - k) = k - j, k = 0~j
 
 dp[i][j] = max(dp[i-1][k] + abs(j - k)) + A[i][j]
 
    rolling part
 = max(dp[i-1][k] + k) - j + A[i][j]
 
 2. j - k <= 0 => - j + k
 
    rolling part
 = max(dp[i-1][k] - k) + j + A[i][j]
 
 
 rolling max:
 
 max(dp[i-1][k] + k) , k = 0 ~ j
 for small to max : start from 0 to n-1 rolling
 
 
 max(dp[i-1][k] - k) , k = j~n-1
 for small to max : start from n-1 to 0 rolling
 
 T: O(mn)
 S: O(mn)
 
*/
```



```
/*
dp[i][j] = Max(dp[i-1][k] - abs(j-k) + point[i][j])

=> 
 for (int i)
  for (int j)
    for (int k)

how to optimized?

j - k >= 0, k = 0~j

dp[i][j] = max(point[i][j] + dp[i-1][k] - j + k)

=>
dp[i][j] = max(dp[i-1][k] + k) + point[i][j] - j

k = 0~j
dp[i][0] = max(dp[i-1][0] + 0) + point[i][0] - 0

dp[i][1] = max(dp[i-1][0] + 0, dp[i-1][1] + 1) + point[i][1] - 1

dp[i][2] = max(dp[i-1][0] + 0, dp[i-1][1] + 1, dp[i-1][2] + 2) + point[i][2] - 2

for (int i)
  for (int j)
    long rollingMax = max(rollingMax, dp[i-1][j] + j)
    dp[i][j] = max(dp[i][j], rollingMax + point[i][j] - j)

----------------------
j - k <= 0, k = j ~ n

dp[i][j] = dp[i-1][k] + j - k

=>
dp[i][j] = dp[i-1][k] - k + j


for (int i)
  for (int j)
    long rollingMax = max(rollingMax, dp[i-1][j] - j)
    dp[i][j] = max(dp[i][j], rollingMax + point[i][j] + j)
    

at last find max in dp[m-1][0~n]
*/
```
