C++刷LeetCode（1937. 扣分后的最大得分*****）【动态规划】【优化】

糖逗

题目描述：

1. 给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。
   
2. 
   
3. 你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。
   
4. 
   
5. 然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行&#160;r 和&#160;r + 1&#160;（其中&#160;0 <= r < m - 1），选中坐标为&#160;(r, c1) 和&#160;(r + 1, c2)&#160;的格子，你的总得分&#160;减少&#160;abs(c1 - c2)&#160;。
   
6. 
   
7. 请你返回你能得到的 最大&#160;得分。
   
8. 
   
9. abs(x)&#160;定义为：
   
10. 
    
11. 如果&#160;x >= 0&#160;，那么值为&#160;x&#160;。
    
12. 如果&#160;x <&#160;0&#160;，那么值为 -x&#160;。
    
13. &#160;
    
14. 
    
15. 示例 1：
    
16. 
    
17. 
    
18. 输入：points = [[1,2,3],[1,5,1],[3,1,1]]
    
19. 输出：9
    
20. 解释：
    
21. 蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
    
22. 你的总得分增加 3 + 5 + 3 = 11 。
    
23. 但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
    
24. 你的最终得分为 11 - 2 = 9 。
    
25. 示例 2：
    
26. 
    
27. 
    
28. 输入：points = [[1,5],[2,3],[4,2]]
    
29. 输出：11
    
30. 解释：
    
31. 蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
    
32. 你的总得分增加 5 + 3 + 4 = 12 。
    
33. 但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
    
34. 你的最终得分为 12 - 1 = 11 。
    
35. &#160;
    
36. 
    
37. 提示：
    
38. 
    
39. m == points.length
    
40. n == points[r].length
    
41. 1 <= m, n <= 105
    
42. 1 <= m * n <= 105
    
43. 0 <= points[r][c] <= 105
    
44. 通过次数2,658提交次数11,536
    
45. 
    
46. 来源：力扣（LeetCode）
    
47. 链接：https://leetcode-cn.com/problems/maximum-number-of-points-with-cost
    
48. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     long long maxPoints(vector<vector<int>>& points) {
   
4.     int m = points.size();
   
5.     int n = points[0].size();
   
6.     vector<long>pre(n);//记录上一行的值
   
7.     //由于某行的dp值只与上一行的值有关，故只需要两个long[n]的数组作为dp数组做状态转移。
   
8.     for (auto point : points) {
   
9.         vector<long>cur(n);//记录这一行的dp值
   
10.         long best = LLONG_MIN;
    
11.         //正序遍历
    
12.         //为何要正序，因为这时是在k在j左边的情况，那么max{dp[i-1][k] + k}中的k可取[0,j]
    
13.         for (int j = 0; j < n; j++) {
    
14.             best = max(best, pre[j] + j);//相当于max{dp[i-1][k] + k}的操作
    
15.             cur[j] = max(cur[j], point[j] - j + best);
    
16.         }
    
17.         best = LLONG_MIN;
    
18.         //倒序遍历
    
19.         //为何要倒序，因为这时是k在j右边的情况，那么max{dp[i-1][k] - k}中的k可取[j,n-1]
    
20.         for(int j = n-1; j >= 0; j--){
    
21.             best = max(best, pre[j] - j);//再倒序遍历，找上一行最大的dp[i-1][k]-k
    
22.             cur[j] = max(cur[j], best + point[j] + j);
    
23.         }
    
24.         pre = cur;
    
25.     }
    
26.     return *max_element(pre.begin(), pre.end());
    
27.     }
    
28. };

复制代码

参考链接：https://leetcode-cn.com/problems ... n-by-leetcode-60zl/   及其中的评论

糖逗

好难想，这道题。看题解想了好久。