题目（难度中等）
给你一个下标从 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 <= 10^5
1 <= grid[i][j] <= 10^6
分析和代码
其移动规律有两个关键点：
（1）从第一列任意位置出发；
（2）每次移动必须到下一列，但是行位置无限制，但是只能三个中的一个row, row-1, row+1；
（3）移动到的位置上的值必须比当前位置大。
DFS
这题可以用DFS求解，但是直接的求解方法会超时：
因为DFS在本题计算时有很多重复计算，所以用数组记录计算值，从而避免重复计算。
代码如下：
class Solution {public:int DFS(int x, int y){// 走到最后一列了if (y == g_grid[0].size()-1){return 0;}// 之前计算过if (g_memo[x][y] != -1){return g_memo[x][y];}int res = 0;for(int i = 0; i < 3; i++){if (x+row_move[i] < g_grid.size() && x+row_move[i]>=0 && g_grid[x+row_move[i]][y+1] > g_grid[x][y]){int cur = DFS(x+row_move[i], y+1);g_memo[x][y] = cur; // 计算值记录res = max(res, cur+1);}}return res;}int maxMoves(vector<vector<int>>& grid) {g_grid = grid;// 初始化计算值记录数组for(int i = 0; i < grid.size(); i++){vector<int> tmp;for (int j = 0; j < grid[0].size(); j++){tmp.push_back(-1);}g_memo.push_back(tmp);}int mm = 0;for(int i = 0; i < grid.size(); i++){mm = max(mm, DFS(i, 0));}return mm;}int row_move[3] = {-1, 0 ,1};vector<vector<int>> g_memo;vector<vector<int>> g_grid;};
复杂度分析：
时间复杂度：O(mn)，其中m 和 n 分别为 grid的行数和列数。动态规划的时间复杂度 = 状态个数× 单个状态的计算时间。本题中状态个数等于 O(mn)，单个状态的计算时间为 O(1)，因此时间复杂度为O(mn)。
空间复杂度：O(mn)。
BFS
这题还可以用BFS进行求解：将每一列视为一个层级,因为对于每条"路线",一个层级(列)只有一个被选择.
代码如下：
class Solution {public:int maxMoves(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();// 序列化数组vector<int> q;for(int i = 0; i < m; i++) q.push_back(i);// 已访问数组vector<int> vis(m,-1);// 按列（每列就是一个层次）移动for(int i = 0; i < n-1; i++){// 复制当前列可以走的位置vector<int> tmp = q;// 下一列可以走的位置q.clear();// 遍历当前列可以走的位置for(auto j : tmp){// 三个移动方向for (int k = 0; k < 3; k++){if (j+move[k] >=0 && j+move[k]<m && vis[j+move[k]]!=i && grid[j+move[k]][i+1] > grid[j][i]){// 标记走过vis[j+move[k]] = i;// 记录下一步q.push_back(j+move[k]);}}}// 下一列没有路了if(q.size() == 0) return i;}// 走到最后一列了，移动步数就是n-1(其实不会执行到这一步)return n-1;}int move[3] = {-1, 0, 1};};
BFS的复杂度如下：
时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(m)。
可以发现BFS比DFS求解更好。
题目链接
https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid
参考链接
https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/solution/cong-ji-yi-hua-sou-suo-dao-di-tui-by-end-pgq3/
