leetcode 1937. 扣分后的最大得分「动态规划」「拆项」

1937. 扣分后的最大得分

题目描述：

给你一个n*m的整数矩阵ar，一开始你的得分为0，你想最大化从矩阵中得到的分数

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加points[r][c]

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少abs(c1 - c2)

请你返回你能得到的 最大 得分

思路：

很经典的拆项思路

$dp[i][j]$表示前$i-1$行均选择了一个格子，第 $i$行选了第$j$个格子，获得的最大价值

很显然状态要从上一行转移过来

• $dp[i][j]=max(dp[i][j],ar[i][j]+dp[i-1][k]-abs(k-j))$

如果这样暴力转移，则时间复杂度是 $O(n\ast m\ast m)$,一定会超时的

我们考虑拆项，根据$k$和$j$的大小，分情况讨论

• $dp[i][j]=max(dp[i][j],tr[i][j]+(dp[i-1][k]+k)-j),k<=j$
• $dp[i][j]=max(dp[i][j],tr[i][j]+(dp[i-1][k]-k)+j),k>j$

对于 $dp[i][j]$我们如果可以用$O(1)$的时间得到 $max\{dp[i-1][k]+k\},k<=j$ 和 $max\{dp[i-1][k]-k\}$的值就行了

所以我们记录一个前缀最大值数组和一个后缀最大值数组，分别记录即可

同时，我们可以发现转移的时候只和上一维度的值有关，可以用滚动数组优化空间

所以最后的时间复杂度是 $O(n\ast m)$

class Solution { public:     long long maxPoints(vector<vector<int>>& tr) {         int n = tr.size(), m = tr[0].size();         vector<long long>dp(m + 1);         vector<long long>pre(m + 2), suf(m + 2);         for(int j = 1; j <= m + 1; ++j){             pre[j] = j;             suf[j] = -j;         }         for(int i = 1; i <= n; ++i){                for(int j = 1; j <= m; ++j){                 dp[j] = tr[i - 1][j - 1] + max(pre[j] - j, suf[j + 1] + j);             }             for(int j = 1; j <= m; ++j){                 pre[j] = max(pre[j - 1], dp[j] + j);             }             for(int j = m; j >= 1; --j){                 suf[j] = max(suf[j + 1], dp[j] - j);             }         }         long long ans = 0;         for(int i = 1; i <= m; ++i)ans = max(ans, dp[i]);         return ans;     } };