329. Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/#/description

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

1
2
3
4
5
6
7
8
9
Example 1:

nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
1
2
3
4
5
6
7
8
9
Example 2:

nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

cpp

Solution 1:

80ms, 75.11%, April.27th, 2016

https://leetcode.com/discuss/81234/solution-with-explanation-search-nearby-using-dfs-easy-read

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if(!m) return 0;
int n = matrix[0].size(), maxSum = 0;
vector<vector<int> > pathSum(m, vector<int>(n , 1));
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
if(pathSum[i][j] == 1)
maxSum = max(maxSum, dfs(matrix, pathSum, m, n, i, j));
return maxSum;
}

private:
int dfs(vector<vector<int>>& matrix, vector<vector<int> > &pathSum, int m, int n, int i, int j){
if(pathSum[i][j] > 1) return pathSum[i][j];
int res = 1;
if(i - 1 >= 0 && matrix[i][j] < matrix[i - 1][j]) res = max(res, 1 + dfs(matrix, pathSum, m, n, i - 1, j));
if(j - 1 >= 0 && matrix[i][j] < matrix[i][j - 1]) res = max(res, 1 + dfs(matrix, pathSum, m, n, i, j - 1));
if(i + 1 < m && matrix[i][j] < matrix[i + 1][j]) res = max(res, 1 + dfs(matrix, pathSum, m, n, i + 1, j));
if(j + 1 < n && matrix[i][j] < matrix[i][j + 1]) res = max(res, 1 + dfs(matrix, pathSum, m, n, i, j + 1));
pathSum[i][j] = res;
return res;
}
};

Solution 2:

429ms, 8.59%, April.27th, 2016

https://leetcode.com/discuss/81855/c-dp-dfs-solution-sharing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int rows = matrix.size();
if(!rows) return 0;
int cols = matrix[0].size();

vector<vector<int>> dp(rows, vector<int>(cols, 0));
std::function<int(int, int)> dfs = [&](int x, int y){
if(dp[x][y]) return dp[x][y];
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
for(auto &dir : dirs){
int xx = x + dir[0], yy = y + dir[1];
if(xx < 0 || xx >= rows || yy < 0 || yy >= cols) continue;
if(matrix[xx][yy] <= matrix[x][y]) continue;
dp[x][y] = std::max(dp[x][y], dfs(xx, yy));
}
return ++dp[x][y];
};

int ret = 0;
for(int i = 0; i < rows; ++i){
for(int j = 0; j < cols; ++j)
ret = std::max(ret, dfs(i, j));
}
return ret;
}
};

python

312ms, 89.28%, 137 / 137, April.27th, 2016

https://leetcode.com/discuss/81747/python-solution-memoization-dp-288ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
def dfs(i, j):
if not dp[i][j]:
val = matrix[i][j]
dp[i][j] = 1 + max(
dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0
)
return dp[i][j]

if not matrix or not matrix[0] : return 0
M, N = len(matrix), len(matrix[0])
dp = [[0]*N for i in xrange(M)]
return max(dfs(x, y) for x in xrange(M) for y in xrange(N))
谢谢你,可爱的朋友。