Longest Increasing Path in a Matrix
HardDynamic Programming
You are given an m x n grid of integers matrix. A path moves from a cell to one of its neighbours directly above, below, left or right (no diagonal moves, no wrapping around the edges), and every step must go to a strictly larger value.
Return the number of cells in the longest such path. A path may start at any cell, and a single cell counts as a path of length 1.
Example 1
- Input:
- matrix = [[5, 4, 8], [6, 3, 9], [1, 2, 7]]
- Output:
- 6
- Explanation
- Start at the
1in the bottom-left, then go right to2, up to3, up to4, left to5and down to6. That path has 6 cells.
Example 2
- Input:
- matrix = [[7, 7], [7, 7]]
- Output:
- 1
- Explanation
- All values are equal, and a step must go to a strictly larger value, so no move is possible. Each path is a single cell.
Example 3
- Input:
- matrix = [[1, 2, 3], [6, 5, 4]]
- Output:
- 6
- Explanation
- The path runs 1, 2, 3 along the top, drops to 4, then runs back left through 5 to 6, using every cell.
Constraints
m == matrix.length,n == matrix[i].length- 1 ≤
m,n≤ 200 - 0 ≤
matrix[i][j]≤ 231 - 1