LeetCode 2684: Maximum Number of Moves in a Grid (Right-to-Left DP on Reachability)
LeetCode 2684Dynamic ProgrammingGridToday we solve LeetCode 2684 - Maximum Number of Moves in a Grid.
Source: https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/
English
Problem Summary
Given an m x n grid, we can start from any cell in column 0. From (r, c), we may move to (r-1, c+1), (r, c+1), or (r+1, c+1) if the destination value is strictly larger. Return the maximum number of moves.
Key Insight
Moves always go from left to right, so dependencies naturally point from column c to c+1. That means we can compute DP from right to left: let dp[r][c] be max moves starting from (r,c). Then each state checks up to 3 next rows in c+1.
Brute Force and Limitations
A DFS from every row in column 0 explores many overlapping subproblems and can blow up exponentially in worst cases. Memoized DFS works, but iterative DP is simpler and cache-friendly.
Optimal Algorithm Steps
1) Initialize dp[r][n-1] = 0 for all rows.
2) For c = n-2 ... 0, for each row r, try rows r-1, r, r+1 in next column.
3) If in bounds and grid[nr][c+1] > grid[r][c], candidate = 1 + dp[nr][c+1].
4) Take max candidate as dp[r][c].
5) Answer is max(dp[r][0]).
Complexity Analysis
Time: O(m * n) (3 transitions per cell).
Space: O(m * n).
Common Pitfalls
- Using >= instead of strict >.
- Forgetting boundary checks for r-1 and r+1.
- Confusing number of visited cells with number of moves (moves = edges, so single cell gives 0).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxMoves(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int c = n - 2; c >= 0; c--) {
for (int r = 0; r < m; r++) {
int best = 0;
for (int nr = r - 1; nr <= r + 1; nr++) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = Math.max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
int ans = 0;
for (int r = 0; r < m; r++) {
ans = Math.max(ans, dp[r][0]);
}
return ans;
}
}func maxMoves(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
for c := n - 2; c >= 0; c-- {
for r := 0; r < m; r++ {
best := 0
for nr := r - 1; nr <= r+1; nr++ {
if nr >= 0 && nr < m && grid[nr][c+1] > grid[r][c] {
cand := 1 + dp[nr][c+1]
if cand > best {
best = cand
}
}
}
dp[r][c] = best
}
}
ans := 0
for r := 0; r < m; r++ {
if dp[r][0] > ans {
ans = dp[r][0]
}
}
return ans
}class Solution {
public:
int maxMoves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int c = n - 2; c >= 0; --c) {
for (int r = 0; r < m; ++r) {
int best = 0;
for (int nr = r - 1; nr <= r + 1; ++nr) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
int ans = 0;
for (int r = 0; r < m; ++r) ans = max(ans, dp[r][0]);
return ans;
}
};from typing import List
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
for c in range(n - 2, -1, -1):
for r in range(m):
best = 0
for nr in (r - 1, r, r + 1):
if 0 <= nr < m and grid[nr][c + 1] > grid[r][c]:
best = max(best, 1 + dp[nr][c + 1])
dp[r][c] = best
return max(dp[r][0] for r in range(m))var maxMoves = function(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let c = n - 2; c >= 0; c--) {
for (let r = 0; r < m; r++) {
let best = 0;
for (let nr = r - 1; nr <= r + 1; nr++) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = Math.max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
let ans = 0;
for (let r = 0; r < m; r++) ans = Math.max(ans, dp[r][0]);
return ans;
};中文
题目概述
给定一个 m x n 的网格，可以从第 0 列任意一行出发。若目标值严格更大，可从 (r,c) 移动到 (r-1,c+1)、(r,c+1) 或 (r+1,c+1)。求最多能走多少步。
核心思路
移动方向固定是“向右一列”，因此状态依赖总是从 c 指向 c+1。最自然的写法是从右往左做 DP：dp[r][c] 表示从 (r,c) 出发最多还能走几步。
暴力解法与不足
如果从每个起点做 DFS，重复子问题很多，最坏会指数级分支。记忆化 DFS可以过，但迭代 DP更直接，边界也更好控。
最优算法步骤
1）初始化最后一列 dp[r][n-1]=0。
2）列指针从 n-2 到 0 逆序遍历。
3）每个格子尝试下一列的三种行位移（上/中/下）。
4）若越界则跳过；若不满足严格递增也跳过。
5）转移式：dp[r][c] = max(1 + dp[nr][c+1])。
6）答案是第一列所有 dp[r][0] 的最大值。
复杂度分析
时间复杂度：O(m * n)（每个格子最多看3个方向）。
空间复杂度：O(m * n)。
常见陷阱
- 把“严格大于”写成了“大于等于”。
- 忘记处理最上行/最下行的边界。
- 把“经过格子数”误当成“移动步数”（本题返回的是步数，起点本身是0步）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxMoves(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int c = n - 2; c >= 0; c--) {
for (int r = 0; r < m; r++) {
int best = 0;
for (int nr = r - 1; nr <= r + 1; nr++) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = Math.max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
int ans = 0;
for (int r = 0; r < m; r++) {
ans = Math.max(ans, dp[r][0]);
}
return ans;
}
}func maxMoves(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
for c := n - 2; c >= 0; c-- {
for r := 0; r < m; r++ {
best := 0
for nr := r - 1; nr <= r+1; nr++ {
if nr >= 0 && nr < m && grid[nr][c+1] > grid[r][c] {
cand := 1 + dp[nr][c+1]
if cand > best {
best = cand
}
}
}
dp[r][c] = best
}
}
ans := 0
for r := 0; r < m; r++ {
if dp[r][0] > ans {
ans = dp[r][0]
}
}
return ans
}class Solution {
public:
int maxMoves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int c = n - 2; c >= 0; --c) {
for (int r = 0; r < m; ++r) {
int best = 0;
for (int nr = r - 1; nr <= r + 1; ++nr) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
int ans = 0;
for (int r = 0; r < m; ++r) ans = max(ans, dp[r][0]);
return ans;
}
};from typing import List
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
for c in range(n - 2, -1, -1):
for r in range(m):
best = 0
for nr in (r - 1, r, r + 1):
if 0 <= nr < m and grid[nr][c + 1] > grid[r][c]:
best = max(best, 1 + dp[nr][c + 1])
dp[r][c] = best
return max(dp[r][0] for r in range(m))var maxMoves = function(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let c = n - 2; c >= 0; c--) {
for (let r = 0; r < m; r++) {
let best = 0;
for (let nr = r - 1; nr <= r + 1; nr++) {
if (nr >= 0 && nr < m && grid[nr][c + 1] > grid[r][c]) {
best = Math.max(best, 1 + dp[nr][c + 1]);
}
}
dp[r][c] = best;
}
}
let ans = 0;
for (let r = 0; r < m; r++) ans = Math.max(ans, dp[r][0]);
return ans;
};
Comments