当前位置：首页 > article >正文

【C++动态规划前缀和】937. 扣分后的最大得分|2105

article 2024/12/25 11:36:50

本文涉及知识点

下载及打开打包代码的方法兼述单元测试
C++动态规划
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

LeetCode1937. 扣分后的最大得分

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

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

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 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 = [[1,2,3],[1,5,1],[3,1,1]]
输出：9
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。
示例 2：
在这里插入图片描述

输入：points = [[1,5],[2,3],[4,2]]
输出：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[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= points[r][c] <= 10⁵

动态规划+前后缀最大值

动态规划的状态表示

dp[r][c] 表示已经处理了r行，最后一行选择的是第c列的最大得分。空间复杂度：O(nm)

动态规划的填表顺序

枚举后序状态，r = 1 to m
一，枚举右移，c从0到C-1。
二，枚举左移，c从C-1到0。

动态规划的转移方程

右移：
x = max(pre[i]+i) i $\in$ [0,c] cur[c] = x - c+ points[r][c];
左移：
x = max(pre[i]-i) i $\in$ [c,C-1] MaxSelf(cur[c],x+c+ points[r][c])
利用前后缀最大值后，单个状态转移的时间复杂度：O(1)，总时间复杂度：O(mn)

动态规划的初始值

dp[0]为0，其它为LLON_MIN/2

动态规划的返回值

dp.back的最大值

代码

核心代码

class Solution {
		public:
			long long maxPoints(vector<vector<int>>& points) {
				const int R = points.size();
				const int C = points.front().size();
				vector<long long> pre(C);
				for (int r = 0; r < R; r++) {
					vector<long long> cur(C);
					long long lMax = INT_MIN;
					for (int c = 0; c < C; c++) {
						lMax = max(lMax, pre[c] + c);
						cur[c] = lMax - c+points[r][c];
					}
					lMax = INT_MIN;
					for (int c = C - 1; c >= 0; c--) {
						lMax = max(lMax, pre[c] - c);
						cur[c] = max(cur[c], lMax + c + points[r][c]);
					}
					pre.swap(cur);
				}
				return *max_element(pre.begin(), pre.end());
			}
		};

单元测试

	vector<vector<int>> points;
		TEST_METHOD(TestMethod11)
		{
			points = { {1,2,3},{1,5,1},{3,1,1} };
			auto res = Solution().maxPoints(points);
			AssertEx(9LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			points = { {1,5},{2,3},{4,2} };
			auto res = Solution().maxPoints(points);
			AssertEx(11LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			points = { {5,3},{3,5},{3,1} };
			auto res = Solution().maxPoints(points);
			AssertEx(11LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			points = { {5,8,6,9,2},{3,2,2,6,0},{2,5,6,10,3},{4,2,1,6,0},{7,3,3,7,5},{4,3,3,0,10},{3,6,5,4,1},{4,5,10,8,6},{10,8,5,0,1},{4,2,9,4,0} };
			auto res = Solution().maxPoints(points);
			AssertEx(75LL, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功