329.Longest Increasing Path in a Matrix

Tags: [DP], [DFS], [Backtracking], [memo], [top_to_bottom_dp]

Com: {g}

Link: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/\#/description

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

Return4
The longest increasing path is[1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return4
The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

Solution: DFS, Backtracking, DP, Memo

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

        num_of_rows = len(matrix)
        num_of_cols = len(matrix[0])

        memo = [[None for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        max_len = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                max_len = max(max_len, 
                              self.helper(matrix, num_of_rows, num_of_cols, row, col, memo))

        return max_len

    def helper(self, matrix, num_of_rows, num_of_cols, row, col, memo):
        if memo[row][col] is not None:
            return memo[row][col]

        remaining_max_len = 0

        # iterate four directions
        # top, left, bottom, right
        directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
        for d in directions:
            r, c = row + d[0], col + d[1]
            if 0 <= r < num_of_rows and 0 <= c < num_of_cols and matrix[r][c] > matrix[row][col]:
                remaining_max_len = max(remaining_max_len, 
                                        self.helper(matrix, num_of_rows, num_of_cols, r, c, memo))

        memo[row][col] = remaining_max_len + 1
        return remaining_max_len + 1

Revelation:

• 一开始我的算法是pass给helper function一个path_len var 用这个var来累积path的总长度，但如果用这种方法就很难用memo，因为如果用二维的memo，例如memo[row][col] 是不对的，因为用这种方法来定义recursion function，要描述当前的状态不能只用row和col，因为path_len也会参与到状态的描述中。
• 用以上的算法，在定义recursion function是只用row和col，这个recursion的意思是：站在当前[row][col]这个点上，能拿到的最长path是多少，所以这样我们就能用row和col来描述当前的状态了，在recursion里我们只要看当前点的四个neighbors，走哪个neighbor可以得到最长的remaining_path即可，然后当前点的longest path的长度 = remaining_max_len + 1.

Note:

• Time complexity = O(num_of_rows * num_of_cols), because we just fill the memo[][], each cell of memo we just compute once.