[LeetCode]Longest Increasing Path in a Matrix

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 大睿-SCTrojan 大睿-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

张贴您的评论