func maxMoves(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for j := n - 2; j >= 0; j-- {
for i, row := range grid {
for k := max(i-1, 0); k < min(i+2, m); k++ {
if grid[k][j+1] > row[j] {
f[i][j] = max(f[i][j], f[k][j+1]+1)
}
}
}
}
for _, r := range f {
ans = max(ans, r[0])
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
class Solution {
public int maxMoves(int[][] grid) {
int m = grid.length, n = grid[0].length;
var f = new int[m][n];
for (int j = n - 2; j >= 0; j--)
for (int i = 0; i < m; i++)
for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, m); k++)
if (grid[k][j + 1] > grid[i][j])
f[i][j] = Math.max(f[i][j], f[k][j + 1] + 1);
int ans = 0;
for (int i = 0; i < m; i++)
ans = Math.max(ans, f[i][0]);
return ans;
}
}
# dp改成递推，
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
f = [[0] * n for _ in range(m)]
for j in range(n - 2, -1, -1):
for i, row in enumerate(grid):
for k in i - 1, i, i + 1:
if 0 <= k < m and grid[k][j + 1] > row[j]:
f[i][j] = max(f[i][j], f[k][j + 1] + 1)
return max(row[0] for row in f)
func maxMoves(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
memo := make([][]int, m)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没被计算过
}
}
var dfs func(int, int) int
dfs = func(i, j int) (res int) {
if j == n-1 {
return
}
p := &memo[i][j]
if *p != -1 {
return *p
}
for k := max(i-1, 0); k < min(i+2, m); k++ {
if grid[k][j+1] > grid[i][j] {
res = max(res, dfs(k, j+1)+1)
}
}
*p = res // 记忆化
return
}
for i := 0; i < m; i++ {
ans = max(ans, dfs(i, 0))
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
'''
写一个递归函数dfs(i,j),返回并记录从(i,j)出发时的答案。
枚举向右边的三个方向走,如果对应的格子没有出界,且格子值大于 grid[i][j],
则有 dfs(i,j) = max(dfs(i-1,j+1)+1,dfs(i,j+1)+1,dfs(i+1,j+1)+1)
递归边界:dfs(i,n-1)=0.
递归入口:dfs(i,0).取最大值即为答案。
'''
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@cache
def dfs(i: int, j: int) -> int:
if j == n - 1:
return 0
res = 0
for k in i - 1, i, i + 1:
if 0 <= k < m and grid[k][j + 1] > grid[i][j]:
res = max(res, dfs(k, j + 1) + 1)
return res
return max(dfs(i, 0) for i in range(m))
func maxMoves(grid [][]int) int {
m, n := len(grid), len(grid[0])
vis := make([]int, m)
q := make([]int, m)
for i := range q {
q[i] = i
}
for j := 0; j < n-1; j++ {
tmp := q
q = nil
for _, i := range tmp {
for k := max(i-1, 0); k < min(i+2, m); k++ {
if vis[k] != j+1 && grid[k][j+1] > grid[i][j] {
vis[k] = j + 1 // 时间戳标记，避免重复创建 vis 数组
q = append(q, k)
}
}
}
if q == nil {
return j
}
}
return n - 1
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
# bfs,每一轮向右搜索一列
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = range(m)
vis = [-1] * m
for j in range(n - 1):
tmp = q
q = []
for i in tmp:
for k in i - 1, i, i + 1:
if 0 <= k < m and vis[k] != j and grid[k][j + 1] > grid[i][j]:
vis[k] = j # 时间戳标记，避免重复创建 vis 数组
q.append(k)
if len(q) == 0:
return j
return n - 1
输入：grid = [[3,2,4],[2,1,9],[1,1,7]] 输出：0 解释：从第一列的任一单元格开始都无法移动。