【C 动态规划】3148. 矩阵中最大的得分

本文涉及知识点。

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。^5。
  1 <= grid[i][j] <= 10。^5。

动态规划。

性质一。：如果路径节点超过或达到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。{。3。,2。,1。}。}。;auto。res。 =Solution。(。)。.。maxScore。(。grid。)。;AssertEx。(。-。1。,res。)。;}。

扩展阅读。

视频课程。

先学简单课程，请移动CSDN学院，听白银讲师（也就是说，鄙人󿂙的讲解。
https://edu.csdn.net/course/detail/38771。
如何快速形成战斗࿰？c;分担老板的烦恼，请学习C#入职培训，C++入职培训等课程。
https://edu.csdn.net/lecturer/6176。

测试环境。

操作系统：win7 开发环境： VS2019。 C++17。
或者 操作系统：win10 开发环境 VS2022。 C++17。
如果没有特别说明󿀌本。算法。用**C++**实现。