剑指 Offer II 112. 最长递增路径 #
- 标签:深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、数组、动态规划、矩阵
- 难度:困难
题目大意 #
给定一个 m * n
大小的整数矩阵 matrix
。要求:找出其中最长递增路径的长度。
对于每个单元格,可以往上、下、左、右四个方向移动,不能向对角线方向移动或移动到边界外。
解题思路 #
深度优先搜索。使用二维数组 record
存储遍历过的单元格最大路径长度,已经遍历过的单元格就不需要再次遍历了。
代码 #
|
|
给定一个 m * n
大小的整数矩阵 matrix
。要求:找出其中最长递增路径的长度。
对于每个单元格,可以往上、下、左、右四个方向移动,不能向对角线方向移动或移动到边界外。
深度优先搜索。使用二维数组 record
存储遍历过的单元格最大路径长度,已经遍历过的单元格就不需要再次遍历了。
|
|