[LeetCode][Python3] 329. Longest Increasing Path in a Matrix

Problem :

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

My Solution :

class Solution:

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

if not matrix or not matrix[0]:

return 0

def find(y, x):

if not memo[y][x]:

val = matrix[y][x]

res = 1

for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):

if (0 <= y+dy < Y and 0 <= x+dx < X and

matrix[y+dy][x+dx] > val):

res = max(res, 1+find(y+dy, x+dx))

memo[y][x] = res

return memo[y][x]

Y, X = len(matrix), len(matrix[0])

memo = [[0]*X for _ in range(Y)]

res = 1

for y in range(Y):

for x in range(X):

res = max(res, find(y, x))

return res

Comment :

전형적인 DFS + Memoization 문제인데, 연습이 부족해서 그런지 매번 쉽게 풀리지 않는다. 비슷한 유형을 수십번 풀어보면 손에 익으려나...