# 1937. Maximum Number of Points with Cost
###### tags: `Leetcode` `Google` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-number-of-points-with-cost/
## 思路
### 原本的思路(TLE) $O(M*N^2)$ $O(N)$
M = points.length
N = points[0].length
dp公式如下
### Optimize之后 $O(M*N)$ $O(N)$
参考[这里](https://leetcode.com/problems/maximum-number-of-points-with-cost/discuss/1344908/C%2B%2BJavaPython-3-DP-Explanation-with-pictures.)
由于肯定要遍历每一行，并且还要遍历每一行中的每一个元素，因此时间复杂度最少为$O(M*N)$
因此差别只在于在遍历每一行的时候怎么在$O(N)$的时间内得到dp array，方法就是记录从左边遍历能得到的最大值和从右边遍历能得到的最大值，接着整行里面每一个位置的值就可以通过算这两个数字的最大值求出
我们先不考虑当前点的score 因为不管是从上一行的哪个点跳到当前点 他们都是固定要加在上面的
唯一改变的就是上一行点的dp值和距离(暂且称他们俩的和为score)
大致的思路是先只考虑左边 如果```left[i-1]```觉得从上一行的```j```点跑到```i-1```这个点的score是最大的 那么对于```left[i]```来说往左的所有点```[0:i-1]```我们只需要考虑上一行的```j```点即可 因为```[0:i-1]```的所有点如果到```i-1```的score比```j```到```i-1```的score小 那么到```i```的score也比```j```到```i```的score小 因为他们是一起减1的
## Code
### Optimize之后

class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[] dp = new long[n];
        for(int i = 0;i < n;i++){
            dp[i] = (long)points[0][i];
        }
        for(int j = 1;j < m;j++){
            long[] left = new long[n];
            long[] right = new long[n];
            long[] temp = new long[n];
            left[0] = dp[0];
            right[n-1] = dp[n-1];
            for(int i = 1;i < n;i++){
                left[i] = Math.max(left[i-1]-1, dp[i]);
            }
            for(int i = n-2;i >= 0;i--){
                right[i] = Math.max(right[i+1]-1, dp[i]);
            }
            for(int i = 0;i < n;i++){
                temp[i] = Math.max(left[i], right[i])+points[j][i];
            }
            dp = temp;
        }
        long ans = 0;
        for(int i = 0;i < n;i++){
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

### 原本的思路(TLE)

class Solution {
    public long maxPoints(int[][] points) {
        long[] dp = new long[points[0].length];
        for(int i = 0;i < points[0].length;i++){
            dp[i] = (long)points[0][i];
        }
        for(int i = 1;i < points.length;i++){
            long[] temp = new long[points[0].length];
            for(int j = 0;j < points[0].length;j++){
                for(int k = 0;k < points[0].length;k++){
                    temp[j] = Math.max(temp[j], dp[k]+points[i][j]-Math.abs(j-k));   
                }
            }
            dp = temp;
        }
        long ans = 0;
        for(int i = 0;i < dp.length;i++){
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}