# DFS & DP solutions

• ``````// 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;
}``````

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