C++刷LeetCode（1937. 扣分后的最大得分*****）【动态规划】【优化】
题目描述：给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。
你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points 。
然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 - c2) 。
请你返回你能得到的 最大 得分。
abs(x) 定义为：
如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。
示例 1：
输入：points = [,,]
输出：9
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。
示例 2：
输入：points = [,,]
输出：11
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
你的总得分增加 5 + 3 + 4 = 12 。
但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
你的最终得分为 12 - 1 = 11 。
提示：
m == points.length
n == points.length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= points <= 105
通过次数2,658提交次数11,536
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-points-with-cost
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
int m = points.size();
int n = points.size();
vector<long>pre(n);//记录上一行的值
//由于某行的dp值只与上一行的值有关，故只需要两个long的数组作为dp数组做状态转移。
for (auto point : points) {
vector<long>cur(n);//记录这一行的dp值
long best = LLONG_MIN;
//正序遍历
//为何要正序，因为这时是在k在j左边的情况，那么max{dp + k}中的k可取
for (int j = 0; j < n; j++) {
best = max(best, pre + j);//相当于max{dp + k}的操作
cur = max(cur, point - j + best);
}
best = LLONG_MIN;
//倒序遍历
//为何要倒序，因为这时是k在j右边的情况，那么max{dp - k}中的k可取
for(int j = n-1; j >= 0; j--){
best = max(best, pre - j);//再倒序遍历，找上一行最大的dp-k
cur = max(cur, best + point + j);
}
pre = cur;
}
return *max_element(pre.begin(), pre.end());
}
};
参考链接：https://leetcode-cn.com/problems/maximum-number-of-points-with-cost/solution/kou-fen-hou-de-zui-da-de-fen-by-leetcode-60zl/ 及其中的评论 本帖最后由 糖逗 于 2021-7-24 18:15 编辑
好难想，这道题。看题解想了好久。{:10_284:}
页:
[1]