O(mn) dp
dp[i][j] = max(dp[i-1][k] + points[i][j] - |j-k|)
对j,k大小分类讨论,两遍扫描就可以
class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
int m = points.size(), n = points[0].size();
vector<vector<long long>> f(m, vector<long long>(n,0));
for (int i = 0;i<n;i++) f[0][i] = points[0][i];
for (int i = 1;i<m;i++){
long long val = -1e9;
for (int j = 0;j<n;j++){
val = max(val, f[i-1][j] + j);
f[i][j] = max(f[i][j], points[i][j] - j + val);
}
val = -1e9;
for (int j = n-1;j>=0;j--){
val = max(val, f[i-1][j] -j);
f[i][j] = max(f[i][j], points[i][j] + j + val);
}
}
long long res = -1e9;
for (int j = 0;j<n;j++) if (f[m-1][j]>res) res = f[m-1][j];
return res;
}
};