# Leetcode 329. Longest Increasing Path in a matrix

## DFS + DP solution

藉由紀錄以前走過的路徑，避免搜索其他節點時，重複搜索相同路徑，達到減少時間複雜度的目的

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        direction_map = [[-1,0],[0,-1],[1,0],[0,1]] # 上下左右
        memo = [[0]*cols for _ in range(rows)] # 紀錄遍歷過的路徑
        output = 0

        def dfs(row: int, col: int):
            if memo[row][col]: # 如果之前遍歷過，直接返回以前的值
                return memo[row][col]
            path = 1
            for _row,_col in direction_map:
                new_row = _row + row
                new_col = _col + col
                if new_row < 0 or new_col < 0 or new_row >= rows or new_col >= cols:
                    continue
                neighbor = matrix[new_row][new_col]
                if neighbor > matrix[row][col]:
                    path = max(path,1 + dfs(new_row,new_col)) # 要加上自己
            memo[row][col] = path
            return path

        for node in range(rows * cols):
            row = node // cols
            col = node % cols
            output = max(output, dfs(row,col))
        return output

## 參考資料

[329 solution with step by step increasing explanation](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/solutions/3242417/329-solution-with-step-by-step-explanation/)