LeetCode의 DP: 점화식을 가진 3개 문제

동적 프로그래밍: 세 가지 LeetCode 문제에 대한 직관적인 접근법

동적 프로그래밍(DP)은 재귀 관계를 통해 계수 및 최적화 문제를 해결합니다. 문제 62(Unique Paths), 64(Minimum Path Sum), 70(Climbing Stairs)을 살펴보겠습니다. 각 문제는 DP의 핵심 특성인 최적 부분 구조와 중복 부분 문제를 보여줍니다.

Unique Paths: 그리드에서 경로 세기

로봇이 m × n 그리드에서 (0,0)에서 (m-1,n-1)로 오른쪽 또는 아래로만 이동합니다. 고유한 경로의 수를 찾으세요.

어떤 경로든 (m-1)개의 아래 단계와 (n-1)개의 오른쪽 단계로 구성됩니다. 조합론적 해법은 이항 계수 C(m+n-2, m-1)을 사용합니다. 그러나 면접에서는 알고리즘적 접근이 기대됩니다.

dp[i][j]를 셀 (i,j)까지의 경로 수로 정의합니다. 재귀 관계:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

경계 조건:

• dp[0][j] = 1 (첫 번째 행)
• dp[i][0] = 1 (첫 번째 열)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

시간 복잡도 O(m·n). 이 해법은 서로소 경로 집합에 대한 덧셈 규칙을 사용합니다.

Minimum Path Sum: 경로 비용 최소화

음수가 아닌 숫자로 구성된 m × n 그리드가 주어집니다. 오른쪽 또는 아래로 이동할 때 (0,0)에서 (m-1,n-1)까지 경로의 값 합계를 최소화하세요.

탐욕 알고리즘(지역 최소 선택)은 실패합니다—높은 값으로 막다른 골목에 이르게 됩니다. 전역 최적화가 필요합니다.

dp[i][j]를 (i,j)에 도달하는 최소 비용으로 정의합니다. 재귀 관계:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

경계 조건:

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

복잡도 O(m·n). 각 값은 모든 후속 셀에 사용됩니다.

Climbing Stairs: DP에서 피보나치 수

n개의 계단(1 ≤ n ≤ 45)을 오르며, 각 단계는 1개 또는 2개의 계단입니다. 방법의 수를 찾으세요.

n=1: 1가지 방법

n=2: 2가지 방법 (1+1, 2)

n=3: 3가지 방법 (1+1+1, 1+2, 2+1)

재귀 관계:

dp[n] = dp[n-1] + dp[n-2]

단순 재귀는 반복 계산으로 인해 지수 복잡도 O(φ^n)를 초래합니다. DP 배열로 문제를 해결합니다:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

최적화된 버전은 두 변수를 사용하여 O(1) 메모리를 사용합니다.

동적 프로그래밍 문제의 징후

두 조건이 충족될 때 DP를 적용하세요:

• 최적 부분 구조: 최적 해법은 부분 문제의 최적 해법으로 구성됩니다.
• 중복 부분 문제: 동일한 부분 문제가 여러 번 계산됩니다.

| 문제 | 최적 부분 구조 | 중복 부분 문제 |

|--------|-------------------------|---------------------------|

| Unique Paths | 인접 셀의 경로 합 | 각 셀까지의 경로가 중복됨 |

| Min Path Sum | 이웃의 최소 비용 | 비용이 아래/오른쪽 모든 셀에 사용됨 |

| Climbing Stairs | n-1과 n-2의 합 | 재귀 호출이 반복됨 |

핵심 요점

• 재귀 관계는 DP의 본질을 정의합니다: dp[i][j]는 인접한 이미 계산된 값에만 의존합니다.
• 경계 조건은 첫 번째 행/열 또는 기본 사례에 대해 별도로 채워집니다.
• 시간 복잡도는 적절한 표 구현으로 항상 O(입력 크기)입니다.
• 메모리는 최적화될 수 있습니다: 그리드의 경우—한 행, 선형 문제의 경우—두 변수.
• 조합론은 종종 수학적 지름길을 제공하지만, 면접에서는 알고리즘적 해법이 더 중요합니다.

— Editorial Team