leetcode329 https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

    本题只优化到记忆化搜索即可，对于严格位置以来比较复杂，无需优化。

    1. /**
    2.  *    
    3.  *
    4.  *    给定一个二维数组matrix,你可以从任何位置出发，走向上下左右四个方向
    5.  *  返回能够走出来的最长的递增链长度。
    6.  */
    7. public class Code05_LongestIncreasingPath {
    9.     // 方式1： 暴力递归
    10.     public static int longestIncreasingPath1(int[][] matrix) {
    11.         int ans = 0;
    12.         int N = matrix.length;
    13.         int M = matrix[0].length;
    14.         for (int i = 0; i < N; i++) {
    15.             for (int j = 0; j < M; j++) {
    16.                 ans = Math.max(ans, process1(matrix, i, j));
    17.             }
    18.         }
    19.         return ans;
    20.     }
    22.     // 从m[i][j]开始走，走出来的最长递增链，返回！
    23.     public static int process1(int[][] m, int i, int j) {
    24.         // base case
    25.         if(i < 0 || i == m.length || j < 0 || j == m[0].length){
    26.             return 0;
    27.         }
    28.         // 不越界 上下左右四个方向
    29.         int up = i > 0 && m[i][j] < m[i - 1][j] ? process1(m, i - 1, j) : 0;
    31.         int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process1(m, i + 1, j) : 0;
    33.         int left = j > 0 && m[i][j] < m[i][j - 1] ? process1(m, i, j - 1) : 0;
    35.         int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process1(m, i, j + 1) : 0;
    37.         return Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    38.     }
    40.     public static int longestIncreasingPath2(int[][] matrix) {
    41.         int ans = 0;
    42.         int N = matrix.length;
    43.         int M = matrix[0].length;
    44.         int[][] dp = new int[N][M];
    45.         for (int i = 0; i < N; i++) {
    46.             for (int j = 0; j < M; j++) {
    47.                 ans = Math.max(ans, process2(matrix, i, j, dp));
    48.             }
    49.         }
    50.         return ans;
    51.     }
    53.     // 从m[i][j]开始走，走出来的最长递增链，返回！
    54.     public static int process2(int[][] m, int i, int j, int[][] dp) {
    55.         if (dp[i][j] != 0) {
    56.             return dp[i][j];
    57.         }
    58.         // (i,j)不越界
    59.         int up = i > 0 && m[i][j] < m[i - 1][j] ? process2(m, i - 1, j, dp) : 0;
    60.         int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process2(m, i + 1, j, dp) : 0;
    61.         int left = j > 0 && m[i][j] < m[i][j - 1] ? process2(m, i, j - 1, dp) : 0;
    62.         int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process2(m, i, j + 1, dp) : 0;
    63.         int ans = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    64.         dp[i][j] = ans;
    65.         return ans;
    66.     }
    68. }