本文涉及知识点

C++动态规划

LeetCode 3148. 矩阵中的最大得分

给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。
你可以从 任一 单元格开始，并且必须至少移动一次。
返回你能得到的 最大 总得分。
示例 1：
输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
输出：9
解释：从单元格 (0, 1) 开始，并执行以下移动：

• 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
• 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。
  总得分为 2 + 7 = 9 。
  示例 2：
  输入：grid = [[4,3,2],[3,2,1]]
  输出：-1
  解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。
  提示：
  m == grid.length
  n == grid[i].length
  2 <= m, n <= 1000
  4 <= m * n <= 10⁵
  1 <= grid[i][j] <= 10⁵

动态规划

性质一：如果路径的节点超过或达到3个，只保留第一个节点和最后一个节点，得分不变。终点行列号都大于等于起点，但两者不能相等。
结论：无论是那种情况：都是枚举(r,c)，求它的右边和下边的最大值iMax。所有 (iMax - grid[r][c])的最大值。

动态规划的状态表示

vMax[r][c]表示 grid[r…R-1][c…C-1]的最大值。 空间复杂度：O(mn)
为了方便处理边界，增加一行一列，值为INT_MAX/2。

动态规划的填表顺序

r = R-1 to 0 c = C-1 to 0

动态规划的转移方程

dp[r][c] = max(dp[r+1][c],dp[r][c+1])
ans = max(ans,dp[r][c]-grid[r][c])
dp[r][c] = max(dp[r][c],grid[r][c])

动态规划的初值

INT_MAX/2

动态规划的返回值

ans

代码

核心代码

	class Solution {
		public:
			int maxScore(vector<vector<int>>& grid) {
				const int R = grid.size(), C = grid[0].size();
				vector<vector<int>> vMax(R + 1, vector<int>(C + 1, INT_MIN / 2));
				int ans = INT_MIN / 2;
				for (int r = R - 1; r >= 0; r--) {
					for (int c = C - 1; c >= 0; c--) {
						vMax[r][c] = max(vMax[r + 1][c], vMax[r][c + 1]);
						ans = max(ans,vMax[r][c] - grid[r][c]);
						vMax[r][c] = max(vMax[r][c], grid[r][c]);
					}
				}
				return ans;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {9,5,7,3},{8,9,6,1},{6,7,14,3},{2,5,3,1} };
			auto res = Solution().maxScore(grid);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {4,3,2},{3,2,1} };
			auto res = Solution().maxScore(grid);
			AssertEx(-1, res);
		}