Leetcode 329. Longest Increasing Path In a Matrix

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

1. 코드

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:

        m, n = len(matrix), len(matrix[0])
        dir = [[-1, 0], [1, 0], [0, 1], [0, -1]]

        def dfs(x, y, dp):
            if dp[x][y] != -1:
                return dp[x][y]

            maxLen = 1 

            for dx, dy in dir:
                nx, ny = x + dx, y + dy

                if 0<=nx and nx<m and 0<=ny and ny<n and matrix[nx][ny] > matrix[x][y]:
                    len = 1 + dfs(nx, ny, dp)
                    maxLen = max(maxLen, len)

            dp[x][y] = maxLen

            return maxLen 

        dp = [[-1]*n for _ in range(m)]
        ans = 0 

        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j, dp))

        return ans 


        

2) 설명

• DFS+DP로 풀어야 하는 문제이다.
• n, m이 200이기 때문에, DFS로만 풀면 O(n^4)의 시간 복잡도로 인해
  시간 초과가 발생한다.
  -> 따라서 Memoization을 통해 코드를 효율적으로 동작시키도록 해야 한다.