[LeetCode][H 0329]行列中最長インクリメントパス(Java)(記憶化検索)

タイトルの説明:
整数行列を指定し、最長のインクリメントパスの長さを見つけます.
各セルについて、上、下、左、右の4つの方向に移動できます.対角線方向に移動したり、境界外に移動したりすることはできません(つまり、周囲を許可しません).
例1:

  : nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
  : 4 
  :         [1, 2, 6, 9]。

例2:

  : nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
  : 4 
  :         [3, 4, 5, 6]。              。

エラーの反省:
①また細かいところで間違えて、なんとプラス記号を忘れてしまいました...
②行列が空であることを無視して、配列の下に境界を越えた.
問題解決の考え方:
記憶化検索、私に与える感じはdfs+dpで、多くくだらないことを言わないで、例1を見ます
シーケンスを増やすため、理論的には、各点が到達できる最大値までの経路長を見つけて記録し、その後、それに着くたびに、この値をそのまま使えばいいのです.
int[][]memo=new int[行数][列数];//最大ロード長を格納するために使用
例1:memo

[                       [
  [9,9,4],     memo      [1,1,2],
  [6,6,8],     ===>      [2,2,1],
  [2,1,1]                [3,4,2]
]                       ] 

    ，         ，dfs           ，  memo   ；    dfs         memo 。

Javaコード(自分のコード):30 ms

//     
//     : 30 ms,  Longest Increasing Path in a Matrix Java      29.14%    
//     : 49.2 MB,  Longest Increasing Path in a Matrix Java      2.94%    
class Solution {
    int row,col;
    int[][] memo;
    int res = 0;
    public int longestIncreasingPath(int[][] matrix) {
        row = matrix.length;
        if(row==0)return 0;
        col = matrix[0].length;
        memo = new int[row][col];
        for(int i=0;i0&&matrix[x-1][y]>matrix[x][y]){
            temp = dfs(matrix,x-1,y)+1;
        }
        //down
        if(xmatrix[x][y]){
            temp = Math.max(temp,dfs(matrix,x+1,y)+1);
        }
        //left
        if(y>0&&matrix[x][y-1]>matrix[x][y]){
            temp = Math.max(temp,dfs(matrix,x,y-1)+1);
        }
        //right
        if(ymatrix[x][y]){
            temp = Math.max(temp,dfs(matrix,x,y+1)+1);
        }
        return memo[x][y]=temp==0?1:temp;
    }
}

より高速なJavaコード:9 ms

//      9 ms    
//            ，        ，   ，，        
class Solution {
    //   dp
    int[][] visited;
    int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        // null  
        if (matrix.length == 0 || matrix[0].length == 0) return 0;

        //   
        m = matrix.length;
        n = matrix[0].length;
        int res = 1;
        visited = new int[m][n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (visited[i][j] != 0) continue;
                res = Math.max(res, dfs(matrix, i, j, Integer.MIN_VALUE));
            }
        }

        return res;
    }

    public int dfs(int[][] matrix, int i, int j, int oldVal){
        //           ，    
        if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] <= oldVal) return 0;
        //             
        if (visited[i][j] == 0){
            //          dfs
            int curVal = matrix[i][j];
            int up = dfs(matrix, i + 1, j, curVal);
            int down = dfs(matrix, i - 1, j, curVal);
            int right = dfs(matrix, i, j + 1, curVal);
            int left = dfs(matrix, i, j - 1, curVal);
            //              
            visited[i][j] = 1 + Math.max(Math.max(up, down), Math.max(right, left));
        }

        return visited[i][j];
    }
}