本文涉及知识点
C++动态规划
LeetCode2684. 矩阵中移动的最大次数
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
示例 1：
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。
示例 2：
输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。
提示：
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106
动态规划
动态规划的状态表示
dp[r][c]表示以(r,c)为起点的最大移动次数。空间复杂度：O(mn)
动态规划的转移方程
（r1,c1）是(r,c)的合法下一个节点，最多3个。iMax = max(dp[r1][c1])，如果不存在则为0。
dp[r][c] = 1 + iMax。
单个状态的转移时间复杂度O(1)，总时间复杂度：O(mn)。预处理，如果排序时间复杂度是:(mnlogmn)，如果用拓扑排序则是O(mn)。
动态规划的填报顺序
值从大到小，可以保证无后效性。
动态规划的初始值
全为0。
动态规划的返回值
dp的最大值
代码
核心代码
class Solution {
public:
int maxMoves(vector<vector<int>>& grid) {
const int R = grid.size();
const int C = grid[0].size();
vector<tuple<int, int, int>> v;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
v.emplace_back(grid[r][c], r, c);
}
}
sort(v.begin(), v.end(), greater<>());
vector<vector<int>> dp(R, vector<int>(C));
int ans = 1;
for (const auto& [tmp, r, c] : v) {
int iMax = 0;
auto NextMax = [&](int iPre, int r1, int c1) {
if ((r1 < 0) || (r1 >= R))return;
if ((c1 < 0) || (c1 >= C))return;
if (grid[r1][c1] <= iPre)return;
iMax = max(iMax, dp[r1][c1]);
};
NextMax(grid[r][c],r - 1, c + 1);
NextMax(grid[r][c], r , c + 1);
NextMax(grid[r][c], r + 1, c + 1);
dp[r][c] = iMax + 1;
if(0 == c ) ans = max(ans, dp[r][c]);
}
return ans-1;
}
};
单元测试
vector<vector<int>> grid;
TEST_METHOD(TestMethod11)
{
grid = { {2,4,3,5},{5,4,9,3},{3,4,2,11},{10,9,13,15} };
auto res = Solution().maxMoves(grid);
AssertEx(3, res);
}
TEST_METHOD(TestMethod12)
{
grid = { {3,2,4},{2,1,9},{1,1,7} };
auto res = Solution().maxMoves(grid);
AssertEx(0, res);
}
TEST_METHOD(TestMethod13)
{
grid = { {65,200,263,220,91,183,2,187,175,61,225,120,39},{111,242,294,31,241,90,145,25,262,214,145,71,294},{152,25,240,69,279,238,222,9,137,277,8,143,143},{189,31,86,250,20,63,188,209,75,22,127,272,110},{122,94,298,25,90,169,68,3,208,274,202,135,275},{205,20,171,90,70,272,280,138,142,151,80,122,130},{284,272,271,269,265,134,185,243,247,50,283,20,232},{266,236,265,234,249,62,98,130,122,226,285,168,204},{231,24,256,101,142,28,268,82,111,63,115,13,144},{277,277,31,144,49,132,28,138,133,29,286,45,93},{163,96,25,9,3,159,148,59,25,81,233,127,12},{127,38,31,209,300,256,15,43,74,64,73,141,200} };
auto res = Solution().maxMoves(grid);
AssertEx(3, res);
}
