329矩阵中的最长递增路径

• 递归 ```java public int longestIncreasingPath(int[][] matrix) {

    int longest = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            longest = Math.max(longest, process(matrix, i, j));
        }
    }
    return longest;

  }

// 法一：递归
public int process(int[][] matrix, int i, int j) {
    int next = 0;
    if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
        next = Math.max(next,process(matrix, i - 1, j));
    }
    if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
        next = Math.max(next,process(matrix, i + 1, j));

    }
    if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
        next = Math.max(next,process(matrix, i, j - 1));

    }
    if (j + 1 < matrix.length && matrix[i][j + 1] > matrix[i][j]) {
        next = Math.max(next,process(matrix, i , j + 1));

    }
    return 1 + next;
}

- 优化： 只要行跟列定了，结果就定了， 因此可以考虑记忆化搜索， （记忆化搜索和动态规划等效）
```java
 public int longestIncreasingPath(int[][] matrix) {
     int longest = 0;
     int[][] dp = new int[matrix.length][matrix[0].length];
     for (int i = 0; i < matrix.length; i++) {
         for (int j = 0; j < matrix[0].length; j++) {
             longest = Math.max(longest, process(matrix, i, j, dp));
         }
     }
     return longest;
 }


    // 在法一的基础上加记忆化搜索
    public int process(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        int next = 0;
        if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
            next = Math.max(next,process(matrix, i - 1, j, dp));
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            next = Math.max(next,process(matrix, i + 1, j, dp));

        }
        if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
            next = Math.max(next,process(matrix, i, j - 1, dp));

        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            next = Math.max(next,process(matrix, i , j + 1, dp));
        }
        dp[i][j] = 1 + next;
        return 1 + next;
    }