## 题目描述：

LeetCode 329. Longest Increasing Path in a Matrix

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).

Example 1:

```nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
```

Return `4`
The longest increasing path is `[1, 2, 6, 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.

## Python代码：

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
h = len(matrix)
if h == 0: return 0
w = len(matrix[0])

def dfs(x, y):
for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] > matrix[x][y]:
if not dp[nx][ny]: dp[nx][ny] = dfs(nx, ny)
dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
dp[x][y] = max(dp[x][y], 1)
return dp[x][y]

dp = [[0] * w for x in range(h)]
for x in range(h):
for y in range(w):
if not dp[x][y]:
dp[x][y] = dfs(x, y)
return max([max(x) for x in dp])
``````

## Python代码：

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
h = len(matrix)
if h == 0: return 0
w = len(matrix[0])
dp = [[1] * w for x in range(h)]
slist = sorted([(i, j, val)
for i, row in enumerate(matrix)
for j, val in enumerate(row)],
key=operator.itemgetter(2))
for x, y, val in slist:
for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] > matrix[x][y]:
dp[nx][ny] = max(dp[nx][ny], dp[x][y] + 1)
return max([max(x) for x in dp])
``````

## Python代码：

``````def longestIncreasingPath(self, matrix):
matrix = {i + j*1j: val
for i, row in enumerate(matrix)
for j, val in enumerate(row)}
length = {}
for z in sorted(matrix, key=matrix.get):
length[z] = 1 + max([length[Z]
for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
or [0])
return max(length.values() or [0])
``````

Pingbacks已关闭。

1. 大睿-SCTrojan 发布于 2016年3月3日 12:32 #

我有一个问题：我觉得这道题和Word Search I很像，于是套用了那道题的解法，就是纯DFS+Backtracking，但是超时了。是不是因为word search只要找到就可以停止，而这道题需要找到最优解，因此需要穷举所有可能，因此导致超时呢？

2. 在线疯狂 发布于 2016年3月5日 16:41 #

是的，对于这道题目来说相当于穷举，所以会超时。

3. 洪北七 发布于 2016年6月1日 06:21 #

解法II 排序 动态规划 里的dp[x][y]是不是应该指以(x,y)为终点的最长递增路径长度？

4. 在线疯狂 发布于 2016年6月2日 17:07 #

是的，应该是以(x,y)为终点的最长递增路径长度，感谢指正！:D