329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

My Answer 1: Wrong Answer

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        def findingPath(row_begin: int, col_begin: int, matrix: List[List[int]]):
            row_end = len(matrix)-1 
            col_end = len(matrix[0])-1
            
            while (row_begin <= row_end and col_begin <= col_end):
                for i in range(col_begin,col_end+1):
                    res.append(matrix[row_begin][i])
                row_begin += 1

                for i in range(row_begin,row_end+1):
                    res.append(matrix[i][col_end])
                col_end -= 1

                if (row_begin <= row_end):
                    for i in range(col_end,col_begin-1,-1):
                        res.append(matrix[row_end][i])
                    row_end -= 1

                if (col_begin <= col_end):
                    for i in range(row_end,row_begin-1,-1):
                        res.append(matrix[i][col_begin])
                    col_begin += 1
        
        maxnum = 0
        res = []
        
        if len(matrix) == 0:
            return maxnum
        
        row_begin = 0
        col_begin = 0
        
        for i in range(len(matrix)):
            row_begin = i
            for j in range(len(matrix[i])):
                col_begin = j
                findingPath(row_begin, col_begin, matrix)
                
        return maxnum

54. Spiral Matrix 를 응용해서 matrix 의 각 숫자마다 연속된 spiral 을 찾으려고 했는데...

사방팔방을 다 고려해야되는게 잘 안됐다..^^

DP + DFS

Solution 1: Runtime: 356 ms - 96.52% / Memory Usage: 14.9 MB - 93.29%

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(
                    dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
            return dp[i][j]

        if not matrix or not matrix[0]: return 0
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * N for i in range(M)]
        return max(dfs(x, y) for x in range(M) for y in range(N))

matrix 각 숫자마다 dfs 재귀를 돌려줌

dp[i][j] 가 0 이면 1 (자기자신) + 사방팔방 increasing path 값들 중 최댓값 으로 업데이트
=> 최종적으로 dp 는 max path 의 길이를 갖게 된다

냅다 외워!!!!!!!