LeetCode-329. 矩阵中的最长递增路径

不念不忘少年蓝@ 2024-03-29 15:52 90阅读 0赞

题目来源  
[329. 矩阵中的最长递增路径][329.]

### 暴力递归 ###

public static int longestIncreasingPath1(int[][] matrix) {
        
    		int ans = 0;
    		int N = matrix.length;
    		int M = matrix[0].length;
    		for (int i = 0; i < N; i++) {
        
    			for (int j = 0; j < M; j++) {
        
    				ans = Math.max(ans, process1(matrix, i, j));
    			}
    		}
    		return ans;
    	}
    
    	// 从m[i][j]开始走，走出来的最长递增链，返回！
    	public static int process1(int[][] m, int i, int j) {
        
    		int up = i > 0 && m[i][j] < m[i - 1][j] ? process1(m, i - 1, j) : 0;
    		int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process1(m, i + 1, j) : 0;
    		int left = j > 0 && m[i][j] < m[i][j - 1] ? process1(m, i, j - 1) : 0;
    		int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process1(m, i, j + 1) : 0;
    		return Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    	}

会发现答案是正确，我们就要继续优化  
![在这里插入图片描述][cc61baa1db304a3a9b015d7864bb013b.png]

### 暴力递归加缓存 ###

定义一个dp

public static int longestIncreasingPath2(int[][] matrix) {
        
    		int ans = 0;
    		int N = matrix.length;
    		int M = matrix[0].length;
    		int[][] dp = new int[N][M];
    		for (int i = 0; i < N; i++) {
        
    			for (int j = 0; j < M; j++) {
        
    				ans = Math.max(ans, process2(matrix, i, j, dp));
    			}
    		}
    		return ans;
    	}
    
    	// 从m[i][j]开始走，走出来的最长递增链，返回！
    	public static int process2(int[][] m, int i, int j, int[][] dp) {
        
    		if (dp[i][j] != 0) {
        
    			return dp[i][j];
    		}
    		// (i,j)不越界
    		int up = i > 0 && m[i][j] < m[i - 1][j] ? process2(m, i - 1, j, dp) : 0;
    		int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process2(m, i + 1, j, dp) : 0;
    		int left = j > 0 && m[i][j] < m[i][j - 1] ? process2(m, i, j - 1, dp) : 0;
    		int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process2(m, i, j + 1, dp) : 0;
    		int ans = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    		dp[i][j] = ans;
    		return ans;
    	}

![在这里插入图片描述][0b92905657dd48e78fda7f932605b531.png]

[329.]: https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
[cc61baa1db304a3a9b015d7864bb013b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/75abeededcc941aeb22b3db979d1f496.png
[0b92905657dd48e78fda7f932605b531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/5d31b79cb81d44f582b9bd6519f3572b.png