Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in the 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). The path must be strictly increasing.
Examples
Input: [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Input: [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Hints
Start by implementing a recursive DFS function that explores all four possible directions from a given cell, ensuring the next cell's value is strictly greater than the current cell's value.
Optimize the DFS by memoizing the results of subproblems (i.e., store the longest increasing path length starting from each cell to avoid redundant calculations).
Use dynamic programming to iteratively compute the longest increasing path for each cell by processing cells in a topological order (e.g., sorted by their values in ascending order) and updating the DP table based on valid neighbors.
Related Problems
Longest Increasing Path in a Matrix
Given an `m x n` integers matrix, return the length of the longest increasing path in the matrix.