Leetcode: Longest Increasing Path in a Matrix
LeetCode in path matrix Longest Increasing
2023-09-11 14:14:07 时间
Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Return 4 The longest increasing path is [1, 2, 6, 9]. Example 2: nums = [ [3,4,5], [3,2,6], [2,2,1] ] Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
DFS + DP:
use a two dimensional matrix dp[i][j] to store the length of the longest increasing path starting at matrix[i][j]
transferring function is: dp[i][j] = max(dp[i][j], dp[x][y] + 1), where dp[x][y] is its neighbor with matrix[x][y] > matrix[i][j]
Note:
- Use
matrix[x][y] > matrix[i][j]
so we don't need avisited[m][n]
array - The key is to
cache
the distance because it's highly possible to revisit a cell
Follow Up: How to get the actual longest increasing path
我的想法:类似Largest Divisible Subset, 除了一个dp[i][j]记录longest length以外,另外再用一个matrix pre[i][j]记录(i,j)longest increasing path上一跳位置, 并用一个variable记录最后最长的path的起始位置(第19行每次res更新时更新)。最后通过这个起始位置沿着一个一个上一跳位置,可以求出path
1 public class Solution { 2 int[][] dp; 3 int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; 4 int m; 5 int n; 6 7 public int longestIncreasingPath(int[][] matrix) { 8 if (matrix==null || matrix.length==0 || matrix[0].length==0) return 0; 9 m = matrix.length; 10 n = matrix[0].length; 11 dp = new int[m][n]; 12 13 int result = 0; 14 15 for (int i=0; i<m; i++) { 16 for (int j=0; j<n; j++) { 17 if (dp[i][j] == 0) 18 dp[i][j] = DFS(i, j, matrix); 19 result = Math.max(result, dp[i][j]); 20 } 21 } 22 return result; 23 } 24 25 public int DFS(int i, int j, int[][] matrix) { 26 if (dp[i][j] != 0) return dp[i][j]; 27 dp[i][j] = 1; 28 for (int[] dir : directions) { 29 int x = i + dir[0]; 30 int y = j + dir[1]; 31 if (x<0 || y<0 || x>=m || y>=n || matrix[x][y]<=matrix[i][j]) continue; 32 dp[i][j] = Math.max(dp[i][j], DFS(x, y, matrix)+1); 33 } 34 return dp[i][j]; 35 } 36 }
相关文章
- Java实现 LeetCode 821 字符的最短距离(暴力)
- Java实现 LeetCode 482 密钥格式化
- Java实现 LeetCode 352 将数据流变为多个不相交区间
- Java实现 LeetCode 283 移动零
- (LeetCode 153)Find Minimum in Rotated Sorted Array
- (LeetCode 169) Majority Element
- [LeetCode] Longest Increasing Path in a Matrix
- [LeetCode] Reverse Words in a String
- [LeetCode] Find Minimum in Rotated Sorted Array
- Leetcode学习计划之动态规划入门day18(300,376)
- leetcode 322. 零钱兑换
- Matlab:成功解决In an assignment A(I)=B,the number of elements in B and I must be the same
- Leetcode 733. 图像渲染(牛,做出来了)
- Leetcode 292. Nim 游戏
- [LeetCode] 41. First Missing Positive ☆☆☆☆☆(第一个丢失的正数)
- leetcode 191 二进制中1的个数 js 实现
- Leetcode:Swap Nodes in Pairs 单链表相邻两节点逆置
- LeetCode-Reverse Words in a String
- LeetCode:Populating Next Right Pointers in Each Node
- leetcode Kth Largest Element in a Stream——要熟悉heapq使用
- leetcode 387. First Unique Character in a String
- leetcode 378. Kth Smallest Element in a Sorted Matrix
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found