[数据结构与算法]【每日一题】LeetCode1937. 扣分后的最大得分【线性DP】

思路

我们很容易写出下面的DP

for (int i=0; i<m; i++)
  for (int j=0; j<n; j++)
    for (int k=0; k<n; k++)
      dp[i][j] = max(dp[i][j], dp[i-1][k] - abs(j-k) + points[i][j]);

但是时间复杂度O(n^3)在题目所给的数据中是肯定会TLE的，怎么改进呢？
我们将绝对值符号拆开，得到下面的分段转移方程：

dp[i][j] = max{ dp[i-1][k] + k - j  + points[i][j]};    for k<=j
dp[i][j] = max{ dp[i-1][k] - k + j  + points[i][j]};    for k>=j

我们发现对于特定的J，$j+points[i][j]$是定值，变得只有K，又出现了类似于LeetCode1014和LeetCode121这种情况，在扫描J的时候，同时能够得到K的前缀最大值，所以我们可以从前遍历一遍，后面遍历一遍，取个max就得到结果了。

AC代码

C++

typedef long long ll;
class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int m = points.size();
        int n = points[0].size();
        vector<vector<ll>> dp(m,vector<ll>(n,INT_MIN));
        for(int i = 0; i < n; i++) dp[0][i] = points[0][i];
        for(int i = 1; i < m; i++){
            ll maxx = INT_MIN;            
            for (int j = 0; j < n; j++){
                maxx = max(maxx, dp[i-1][j]+j);
                dp[i][j] = max(dp[i][j], maxx + points[i][j] - j);
            }
            
            maxx = INT_MIN;            
            for (int j = n-1; j >= 0; j--){
                maxx = max(maxx, dp[i-1][j]-j);
                dp[i][j] = max(dp[i][j], maxx +points[i][j] + j);
            }
        }
        ll ans = INT_MIN;
        for(int i = 0; i < n; i++) ans = max(ans, dp[m-1][i]);
        return ans;
    }
};