2684. Maximum Number of Moves in a Grid 给一个n*m的二维矩阵里面都是正整数 从第一行任一个元素开始 满足下列条件(row,col)可以往(row-1,col+1)、(row,col+1)、(row-1,col+1)移动 你要目标cell的值比现在cell的值还大 请问最多可以做几次移动? 思路: 就照着题目做 用两个长度为n的dp矩阵 dp1纪录matrix[i][j]有没有路径可以抵达 dp2纪录matrix[i][j+1]有没有路径可以抵达 从第一行开始一直到第m-1行 如果dp1[i] == j表示matrix[i][j]有路径可以抵达 接着去检查三个方向的值有没有比matrix[i][j]大 有的话对应方向的dp2=dp[i]+1 然後把dp1=dp2并建立一个新的dp2，继续下一轮 最後把dp1最大的值回传就好 golang code : func maxMoves(grid [][]int) int { n, m := len(grid), len(grid[0]) tmp1 := make([][]int, 1) tmp1[0] = make([]int, m) tmp2 := make([][]int, 1) tmp2[0] = make([]int, m) grid = append(tmp1, grid...) grid = append(grid, tmp2...) ans := 0 dp1 := make([]int, n+2) dp2 := make([]int, n+2) for j := 0; j < m-1; j++ { for i := 1; i <= n; i++ { if dp1[i] == j { if grid[i][j] < grid[i-1][j+1] { dp2[i-1] = j + 1 ans = max(dp2[i-1], ans) } if grid[i][j] < grid[i][j+1] { dp2[i] = j + 1 ans = max(dp2[i], ans) } if grid[i][j] < grid[i+1][j+1] { dp2[i+1] = j + 1 ans = max(dp2[i+1], ans) } } } dp1 = dp2 dp2 = make([]int, n+2) } return ans } --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.71.212.104 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730210871.A.FE8.html