# 0329. Longest Increasing Path in a Matrix
###### tags: `Leetcode` `Medium` `DFS+Memorization`
Link: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
## 思路
和[2328. Number of Increasing Paths in a Grid](https://hackmd.io/nsHcqQhPTOCJE32B2RX5vA)很像
我们从任意点A开始递归寻找各条递增路径，最终返回的时候记录从A为起点时的最长路径长度。将此结果记忆化，这样当对其他点进行DFS的时候，如果递归调用到dfs(A)就直接返回结果。
## Code

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int maxLen = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int len = dfs(matrix, i, j, cache);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
    private int dfs(int[][] matrix, int x, int y, int[][] cache){
        int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,1}, {0,-1}};
        if(cache[x][y]!=0) return cache[x][y];
        int m = matrix.length;
        int n = matrix[0].length;
        int maxLen = 1;
        for(int[] dir:dirs){
            int nextx = x+dir[0];
            int nexty = y+dir[1];
            if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && matrix[nextx][nexty]>matrix[x][y]){
                maxLen = Math.max(maxLen, 1+dfs(matrix, nextx, nexty, cache));
            }
        }
        return cache[x][y] = maxLen;
    }
}