DFS & DP solutions


  • -1
    L
    // DFS
    function longestIncreasingPath(matrix) {
      var map = [];
      var x, y;
      var dimX = matrix.length;
      var dimY = dimX ? matrix[0].length : 0;
      var max = 0;
    
      for (x = 0; x < dimX; x++) map[x] = [];
    
      for (x = 0; x < dimX; x++)
        for (y = 0; y < dimY; y++)
          max = Math.max(max, dfs(x, y));
    
      return max;
    
    
      function dfs(x, y) {
        var max = 0;
        if (!map[x][y]) {
          var v = matrix[x][y];
          if (matrix[x + 1] && matrix[x + 1][y] && matrix[x + 1][y] > v)
            max = Math.max(max, dfs(x + 1, y));
          if (matrix[x - 1] && matrix[x - 1][y] && matrix[x - 1][y] > v)
            max = Math.max(max, dfs(x - 1, y));
          if (matrix[x][y + 1] && matrix[x][y + 1] > v)
            max = Math.max(max, dfs(x, y + 1));
          if (matrix[x][y - 1] && matrix[x][y - 1] > v)
            max = Math.max(max, dfs(x, y - 1));
          map[x][y] = max + 1;
        }
        return map[x][y];
      }
    }
    
    // DP
    function longestIncreasingPath(matrix) {
      var longestCount = [];
      var max = 0,
        k, x, y, tmp, dimX = matrix.length,
        dimY = dimX ? matrix[0].length : 0;
      for (x = 0; x < dimX; x++) {
        longestCount[x] = [];
        for (y = 0; y < dimY; y++)
          longestCount[x][y] = 1;
      }
    
      for (k = 0; k < dimX * dimY; k++) {
        tmp = 0;
        for (x = 0; x < dimX; x++) {
          for (y = 0; y < dimY; y++) {
            if (matrix[x - 1] && matrix[x - 1][y] && matrix[x - 1][y] > matrix[x][y])
              longestCount[x][y] = Math.max(longestCount[x][y], longestCount[x - 1][y] + 1);
            if (matrix[x + 1] && matrix[x + 1][y] && matrix[x + 1][y] > matrix[x][y])
              longestCount[x][y] = Math.max(longestCount[x][y], longestCount[x + 1][y] + 1);
            if (matrix[x][y - 1] && matrix[x][y - 1] > matrix[x][y])
              longestCount[x][y] = Math.max(longestCount[x][y], longestCount[x][y - 1] + 1);
            if (matrix[x][y + 1] && matrix[x][y + 1] > matrix[x][y])
              longestCount[x][y] = Math.max(longestCount[x][y], longestCount[x][y + 1] + 1);
            tmp = Math.max(tmp, longestCount[x][y]);
          }
        }
        if (tmp === max && k >= tmp) return max;
        max = Math.max(tmp, max);
      }
      return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.