演算法練習 Leetcode 力扣 329. Longest Increasing Path in a Matrix 解法

feellikelearning June 21, 2020 0 Comments

這題不知道為什麼被標記為topological sort，但其實和topological sort沒什麼關係，只是DFS。Implementation確實和DFS的topological sort有點像，但是因為沒有graph的dependency關係，其實還是不一樣的。不過cache的使用上確實有相似性。以下是我寫得比較滿意的python解法

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if (matrix is None or len(matrix) == 0 or  
                matrix[0] is None or len(matrix[0]) == 0):
                return 0
        lines = len(matrix)
        cols = len(matrix[0])
        
        cache = [[0] * len(line) for line in matrix]
        
        def is_valid(i, j):
            return i >= 0 and i < lines and j >= 0 and j < cols
        
        max_l = 0
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        
        def dfs(i: int, j: int) -> int:
            if cache[i][j] > 0:
                return cache[i][j]
            for d in dirs:
                i2 = i + d[0]
                j2 = j + d[1]
                if is_valid(i2, j2) and matrix[i2][j2] > matrix[i][j]:
                    cache[i][j] = max(cache[i][j], dfs(i2, j2))
            cache[i][j] += 1
            nonlocal max_l
            max_l = max(max_l, cache[i][j])
            return cache[i][j]
        
        for i in range(lines):
            for j in range(cols):
                dfs(i, j)
                
        return max_l

要點總結：

1. 用這種方式初始化cache比較簡潔 ，新學到的 cache = [[0] * len(line) for line in matrix]
2. 用nested function大大減少需要傳遞狀態的參數
3. nonlocal max_l可以讓nested function直接改變外面的參數很方便，所以在外面call dfs的時候連return都不用處理
4. dirs = [(1,0), (-1,0), (0,1), (0,-1)]，i2 = i + d[0]，j2 = j + d[1]處理方向。以前都是手寫上下左右，太啰嗦而且容易出錯。這種方法對2維DFS很適用。