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

[1, 2, 6, 9]

Return 4

思路：dp[i][j]代表matrix中以i, j结尾的情况，LIP的长度。 递推公式当然就是dp[i][j] = max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + 1 。然后我们发现这个dp[i][j]居然是由4个不同方向的决定的，如果用for loop来实现就会很日狗。所以我们就用memo，把算过的存起来。整体实现方法是dfs，遍历matrix中的每一个点。如果算过就直接返回长度，如果没算过就继续dfs下去。复杂度嘛。O(m*n)因为不会重复计算，每个点访问一次。

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

jiuzhang http://www.lintcode.com/en/problem/longest-increasing-continuous -subsequence-ii/

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix or not matrix[0]: return 0
        self.m, self.n = len(matrix), len(matrix[0])
        self.memo = [[0]*self.n for _ in range(self.m)]
        return max(self.dfs(i, j, matrix) for i in range(self.m) for j in range(self.n))

    def dfs(self, i, j, matrix):
        if not self.memo[i][j]:
            val = matrix[i][j]
            self.memo[i][j] = 1+ max(
                self.dfs(i+1, j, matrix) if i < self.m - 1 and val < matrix[i+1][j] else 0,
                self.dfs(i-1, j, matrix) if i and val < matrix[i-1][j] else 0,
                self.dfs(i, j+1, matrix) if j < self.n - 1 and val < matrix[i][j+1] else 0,
                self.dfs(i, j-1, matrix) if j and val < matrix[i][j-1] else 0)
        return self.memo[i][j]

另外一一种写法 直接dfs暴力解：

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]: return 0
    n, m = len(matrix), len(matrix[0])
    count = 0

    visited = [[0]*m for i in range(n)]

    for i in range(n):
        for j in range(m):
            count = max(dfs(i, j, 1, matrix), count)
    return count

def dfs(i, j, count, matrix):
    tmp = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)] 
    neib = [matrix[w][c] for w, c in tmp if 0<=w<len(matrix) and 0<=c<len(matrix[0]) ]

    if matrix[i][j]>=max(neib):
        return count
    result = []
    for w, c in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
        if 0<=w<len(matrix) and 0<=c<len(matrix[0]):
            if matrix[i][j]<matrix[w][c]:
                result.append(dfs(w, c, count+1, matrix))
    return max(result)