西安网站建设公司有哪些,学校网站开发4人小组分工,青岛网站建设技术托管,源代码管理网站题目链接 思路
方法一#xff1a;dfs暴力回溯 使用原始used数组4个方向遍历框架 #xff0c; 全局添加一个最大值判断最大的路径长度。 方法二#xff1a;加上dp数组记忆的优雅回溯 抛弃掉used数组#xff0c;使用dp数组来记忆遍历过的节点的最长递增路径长度。每遍历到已…题目链接 思路
方法一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_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
方法二代码
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_max1return my_max1
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 这道题的dp卡了我很久。让我好几天都没有刷题的欲望。在需要机械化完成的任务面前情绪更多时候真的是没用的东西。反正都要做的早做晚做都是要做开心也要做不开心也要做倒不如不怀情绪地认真做。别急
