题目描述

blablabla

样例

blablabla

blablabla

/*
相当于一个有向无环图，每个点都有四个方向可以走
1. backtracking， 以matrix[i][j]为end的最长边长是多少
    1. 什么是一个解: 没走一步，都是一个解，和ans比较
    2. 分支是什么: 三个方向
    3. 在哪收集解，每一步都是一个解
    Time complexity O(3 ^ m*n)
    Space complexity O(M * N)
    backtrack 超时
    这里不需要mark visited，是因为递增的，不可能再往回走，走过的点了,所以不需要
*/

class Solution {
    int ans = 0;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    public int longestIncreasingPath(int[][] matrix) {
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                backtracking(i, j, 1, matrix);
            }
        }
        return ans;
    }

    public void backtracking(int x, int y, int cur, int[][] matrix){
        ans = Math.max(ans, cur);
        for(int k = 0; k < 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx >= 0 && ny >= 0 && nx < matrix.length && ny < matrix[0].length && matrix[nx][ny] > matrix[x][y]){
                backtracking(nx, ny, cur + 1, matrix);
            }
        }
    }
}







    区别：Pure recursion和backtracking， function的定义不同
    Pure recursion 是以一个点为开始的path: 定义是以这个点为开始的，因为是由下到上，由子问题返回来的
    Backtracking是以一个点为结尾的path: 定义是以这个点为end的，因为是由上到下，一点一点加的
    不需要mark visited这道题，因为longest Increasing，往大的走，就不可能走回来

优化:
        1
1      2    1
        1
这种队形的，就有重复运算了， 每个1都要调用一遍2

/*
相当于一个有向无环图，每个点都有四个方向可以走
2. recursion + memo
    recursion 定义: 以i，j为start的最长的路径
    base case: local maximum
                memo[i][j] > 0
    subproblem: 4个方向
    recursion rule:
        longest = 1
        if(matrix[nx][ny] > matrix[x][y])
            longest = Math.max(四个方向 + 1, longest)
        memo[i][j] = longest;  
        因为是以i，j为start， 得到longest的时候，已经遍历好四个方向上所有的子问题了，所以不会有longest，不是longest的情况

    O(mn)
*/
/*
相当于一个有向无环图，每个点都有四个方向可以走
2. recursion + memo
    recursion 定义: 以i，j为start的最长的路径
    base case: local maximum
                memo[i][j] > 0
    subproblem: 4个方向
    recursion rule:
        longest = 1
        if(matrix[nx][ny] > matrix[x][y])
            longest = Math.max(四个方向 + 1, longest)
        memo[i][j] = longest;  
        因为是以i，j为start， 得到longest的时候，已经遍历好四个方向上所有的子问题了，所以不会有longest，不是longest的情况

    O(mn)
*/
class Solution {
    int ans = 0;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int[][] memo;
    public int longestIncreasingPath(int[][] matrix) {
        memo = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                ans = Math.max(ans, recursion(i, j, matrix));
            }
        }
        return ans;
    }

    public int recursion(int x, int y, int[][] matrix){
        if(memo[x][y] > 0) return memo[x][y];
        int longest = 1; 
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < matrix.length && ny < matrix[0].length && matrix[nx][ny] > matrix[x][y]){
                longest = Math.max(recursion(nx, ny, matrix) + 1, longest);
            }
        }
        memo[x][y] = longest;
        return  longest;
    }
}

blablabla
```