Longest Increasing Path in a Matrix

强化班里给的方法是通过DFS搜索加备忘，任何一个已经搜过的点直接返回距离而不用再重新搜了，这样的DFS时间复杂度还是O(nm)，这里利用上升路径还是下降路径都是可以的，Python的二维三维数组初始化尽量用for循环，乘号初始化经常有引用问题发生

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

        m = len(matrix[0])
        if not m:
            return 0

        distance = [[[1, False] for _ in xrange(m)] for _ in xrange(n)]
        result = 1
        for i in xrange(n):
            for j in xrange(m):
                if not distance[i][j][1]:
                    result = max(result, self.DFS(i, j, matrix, distance, n, m))
                else:
                    result = max(result, distance[i][j][0])

        return result

    def DFS(self, row, col, matrix, distance, n, m):
        if distance[row][col][1]:
            return distance[row][col][0]

        for i, j in [[1,0], [0,1], [-1,0], [0,-1]]:
            curRow, curCol = row + i, col + jf
            if 0 <= curRow < n and 0 <= curCol < m:
                if matrix[row][col] < matrix[curRow][curCol]:
                    distance[row][col][0] = max(distance[row][col][0], self.DFS(curRow, curCol, matrix, distance, n, m) + 1)

        distance[row][col][1] = True
        return distance[row][col][0]

北大的算法课上面关于这道题有一个先把坐标按照高度排序之后再逐个根据高度给他们的相邻点加高度的方法，这样做实际上已经完全摆脱了DP的思维，有点像拓扑排序这种感觉，而且因为排序的存在，时间复杂度应该是O(nmlg(nm))，但是实际表现上这个算法比上面的记忆化DP要好很多

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

        m = len(matrix[0])
        if not m:
            return 0

        distance = [[1] * m for _ in xrange(n)]
        relativeAlt = [[matrix[i][j], i, j] for i in xrange(n) for j in xrange(m)]
        relativeAlt.sort(key=lambda entry: entry[0])

        result = 1
        for node in relativeAlt:
            value, row, col = node
            if 0 <= row - 1 and value < matrix[row - 1][col]:
                distance[row - 1][col] = max(distance[row - 1][col], distance[row][col] + 1)
                result = max(result, distance[row - 1][col])
            if 0 <= col - 1 and value < matrix[row][col - 1]:
                distance[row][col - 1] = max(distance[row][col - 1], distance[row][col] + 1)
                result = max(result, distance[row][col - 1])
            if row + 1 < n and value < matrix[row + 1][col]:
                distance[row + 1][col] = max(distance[row + 1][col], distance[row][col] + 1)
                result = max(result, distance[row + 1][col])
            if col + 1 < m and value < matrix[row][col + 1]:
                distance[row][col + 1] = max(distance[row][col + 1], distance[row][col] + 1)
                result = max(result, distance[row][col + 1])

        return result

上面这种方法隐含的思维其实还是和记忆化搜索一样，一个点的最长距离肯定来自于它四边中比它矮的那些选择中最长的一条路径，我们把所有点按照高度排序了之后，一个点的四边能选择的点肯定在轮到这个点来做决定的时候已经得到最大结果了，这样我们只需要选择其中最长的那个就行了