（补）算法刷题Day24: BM61 矩阵最长递增路径

embedded/2024/12/24 9:11:42/

题目链接

思路

方法一：dfs暴力回溯
使用原始used数组+4个方向遍历框架 =，全局添加一个最大值判断最大的路径长度。
方法二：加上dp数组记忆的优雅回溯
抛弃掉used数组，使用dp数组来记忆遍历过的节点的最长递增路径长度。每遍历到已经记录过的坐标，就直接返回即可。

方法一代码

python">import copy
max_result_len = -1
result = []
direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(matrix, used, row_n, col_m, x, y, path):# 判断是否合法global max_result_lenglobal resultif len(path) > max_result_len:max_result_len = len(path)print(max_result_len)print(path)result = copy.deepcopy(path)if x < 0 or y < 0 or x >= row_n or y >= col_m:returnif used[x][y]:return# 如果当前节点值是小于前一个，则passif matrix[x][y] <= path[-1]:returnused[x][y] = Truepath.append(matrix[x][y])for dx, dy in direct:nx = x + dxny = y + dydfs(matrix, used, row_n, col_m, nx, ny, path)used[x][y] = Falsepath.pop()
class Solution:def solve(self, matrix: List[List[int]]) -> int:# write code hererow = len(matrix)col = len(matrix[0])used = [[False for _ in range(row)] for _ in range(col)]for i in range (row):for j in range (col):dfs(matrix, used, row, col, i, j, [-1])return max_result_len-1

方法二代码

python">direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]def dfs(matrix, row_n, col_m, x, y, path,dp):# 判断是否合法if x < 0 or y < 0 or x >= row_n or y >= col_m:return 0# 如果当前节点值是小于前一个，则passif matrix[x][y] <= path[-1]:return 0# 如果 dp 记录过就直接加上if dp[x][y] != -1:return dp[x][y]path.append(matrix[x][y])my_max = -1for dx, dy in direct:nx = x + dxny = y + dysub_max = dfs(matrix, row_n, col_m, nx, ny, path,dp)my_max = max(sub_max,my_max)path.pop()dp[x][y] = my_max+1return my_max+1
class Solution:def solve(self, matrix: List[List[int]]) -> int:row = len(matrix)col = len(matrix[0])dp = [[-1 for _ in range(row)]for _ in range(col)]max_result_len = -1for i in range(row):for j in range(col):m = dfs(matrix,row, col, i, j, [-1],dp)max_result_len = max(max_result_len, m)return max_result_len