当前位置：首页 > article >正文

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

article 2025/3/1 7:19:49

题目链接

思路

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

方法一代码

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_len
    global result
    if 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:
        return
    if used[x][y]:
        return
    # 如果当前节点值是小于前一个，则pass
    if matrix[x][y] <= path[-1]:
        return
    used[x][y] = True
    path.append(matrix[x][y])
    for dx, dy in direct:
        nx = x + dx
        ny = y + dy
        dfs(matrix, used, row_n, col_m, nx, ny, path)
    used[x][y] = False
    path.pop()
class Solution:
    def solve(self, matrix: List[List[int]]) -> int:
        # write code here
        row = 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

方法二代码

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
    # 如果当前节点值是小于前一个，则pass
    if matrix[x][y] <= path[-1]:
        return 0
    # 如果 dp 记录过就直接加上
    if dp[x][y] != -1:
        return dp[x][y]
    path.append(matrix[x][y])
    my_max = -1
    for dx, dy in direct:
        nx = x + dx
        ny = y + dy
        sub_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+1
    return 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 = -1
        for 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