题目描述：

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.

题目大意：

给定一个整数矩阵，计算其最长递增路径的长度。

从每一个单元格出发，你可以向四个方向移动：左右上下。你不可以沿着对角线移动也不能移出边界。（亦即，环绕是不允许的）。

测试用例如题目描述。

解题思路：

解法I 记忆化搜索（DFS + Memoization）：

枚举起点，从每一个单元格出发，递归寻找其最长递增路径。

利用辅助数组dp记录已经搜索过的单元格，dp[x][y]存储从单元格(x, y)出发的最长递增路径长度。

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

解法II 排序+动态规划（Sort + Dynamic Programming）：

将矩阵matrix按照值从小到大排序，得到列表slist，列表元素(x, y, val)存储原矩阵的(行、列、值)

引入辅助数组dp，dp[x][y]表示以矩阵(x, y)元素为终点的最长递增路径长度

遍历slist，同时更新(x, y)左、右、上、下四个相邻元素的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])

参考：https://leetcode.com/discuss/81319/short-python

代码作者使用复数表示矩阵的行、列，十分巧妙。

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

 

本文链接：http://bookshadow.com/weblog/2016/01/20/leetcode-longest-increasing-path-matrix/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码