Description
Given an m x n matrix, find the length of the longest increasing path. You can move in 4 directions. Use DFS with memoization.
Examples
Input:
matrix = [[9,9,4],[6,6,8],[2,1,1]]Output:
4Explanation:
Path: 1 -> 2 -> 6 -> 9
Input:
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]Output:
7Explanation:
The longest increasing path has length 4. One such path is 6->7->8->12, moving right along the second row and then down. Each step increases strictly.
Input:
matrix = [[7,8,9],[4,5,6],[1,2,3]]Output:
9Explanation:
The longest strictly increasing path has length 5. One valid path is 1->2->3->6->9, moving right across the first row and then down the last column.
Constraints
- •
1 ≤ m, n ≤ 200 - •
0 ≤ matrix[i][j] ≤ 2³¹ - 1