What is the best way to solve Longest Increasing Path In Matrix?

The optimized O(n) approach using 2D DP patterns is generally preferred.

상위 150개 인터뷰중간

행렬의 가장 긴 증가 경로

'행렬에서 가장 긴 증가 경로' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

m x n 정수 행렬이 주어지면 행렬에서 가장 긴 증가 경로의 길이를 반환합니다.

각 셀에서 왼쪽, 오른쪽, 위, 아래의 네 방향으로 이동할 수 있습니다. 대각선으로 이동하거나 경계 밖으로 이동할 수 없습니다(즉, 순환이 허용되지 않음).

longestIncreasingPath(matrix: List[List[int]]) -> int 함수를 작성하세요.

제약

•m == len(matrix)
•n == len(matrix[0])
•1 <= m, n <= 200
•0 <= matrix[i][j] <= 2^31 - 1

예

Example 1

Input

matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output

Explanation

The longest increasing path is [1, 2, 6, 9].

Example 2

Input

matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output

Explanation

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Need a Hint?

세트나 힙과 같은 2D DP 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

2D DP 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def longest_increasing_path_opt(matrix):
    ROWS, COLS = len(matrix), len(matrix[0]); dp = {}
    def dfs(r, c, prevVal):
        if r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prevVal: return 0
        if (r, c) in dp: return dp[(r, c)]
        res = 1 + max(dfs(r + 1, c, matrix[r][c]), dfs(r - 1, c, matrix[r][c]), dfs(r, c + 1, matrix[r][c]), dfs(r, c - 1, matrix[r][c]))
        dp[(r, c)] = res; return res
    for r in range(ROWS):
        for c in range(COLS): dfs(r, c, -1)
    return max(dp.values())

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def longest_increasing_path_brute(matrix):
    ROWS, COLS = len(matrix), len(matrix[0])
    def dfs(r, c, prev):
        if r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prev: return 0
        return 1 + max(dfs(r+1,c,matrix[r][c]), dfs(r-1,c,matrix[r][c]), dfs(r,c+1,matrix[r][c]), dfs(r,c-1,matrix[r][c]))
    return max(dfs(r, c, -1) for r in range(ROWS) for c in range(COLS))