329. Longest Increasing Path in a Matrix
Question
Given an
m x n
integersmatrix
, return *the length of the longest increasing path in *matrix
.From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Solution
第一次就通过DFS和DP的知识自己摸索出了记忆化搜索,非常开心!: )
记忆化搜索,采用DFS搜索,并动态规划的思想保存搜索结果。
递归计算从x, y点出发的最大长度,并在递归中记录子位置的最大长度。
通过子位置的最大长度对递归树进行剪枝。
记忆化搜索
初始化一个memo[][]数组,记录已经搜索过的x, y位置的最大长度。
对所有下一个位置进行DFS搜索,如果越界或不满足递增规律,则返回最大长度1。
(这里应该返回0,但是为了下一步的记忆化搜索判断的遍历因此返回1。如果返回0的话则后面返回最大值不需要-1,但此时由于会重复搜索因此速度会降低。)
如果x, y的位置已经搜索过了(即memo[x][y] != 0),则直接返回memo[x][y]的值+1。
搜索完所有位置的最大长度,将其中的最大值保存在memo[][]中。
最后返回最大值+1。
将每个位置遍历,返回memo[][]中的最大值。
Code
1 | class Solution { |
329. Longest Increasing Path in a Matrix
https://xuanhe95.github.io/2022/05/19/329-Longest-Increasing-Path-in-a-Matrix/