[WIP] 비 CS 담당자가 동적 프로그래밍(DP)을 설명합니다.

요약

방법
찬성
범죄자
시간 복잡도
공간 복잡성


1. 재귀
직관적
시간 제한을 초과할 수 있음
O(d^N), 여기서 d = 각 재귀 단계에서 선택할 수 있는 수
오(1)

2. 메모이제이션(하향식)
직관적, 시간 절약
스택 오버플로 가능
O(N), 모든 반복 함수 호출은 메모/dp 테이블에서 검색됩니다.
켜짐)

3. 표 작성(상향식)
시간 절약
직관적이지 않음
켜짐)
O(1) ~ O(N)


이 게시물이 여러분이 지속적으로 DP Hard 문제를 해결하는 데 도움이 되는 학습 내용을 문서화하기를 바랍니다.

Neetcode Problem List

Memoization VS Tabulation

Memoization (1D, 2D, and 3D)

If I had to count the number of times I solved Fibonacci...

예 1: 계단 오르기(Leetcode: 쉬움)

Here 내 솔루션입니다.

아이디어

재귀는 직관적이지만 TLE입니다.

메모화는 런타임 복잡성을 줄여주지만 스택 오버플로가 발생할 수 있습니다.

도표화는 런타임 복잡성을 줄여주지만 반복 공식을 파악하기는 어렵습니다.

예 2: 경계를 벗어난 경로(Leetcode: Medium)

3D 메모이제이션이 여기서 작동합니다. 극단적인 모드로 Tabulation에 들어갈 필요가 없습니다.

dp = [[[-1] * (maxMove + 1) for _ in range(n+1)] for _ in range(m+1)]

        def dfs(r,c,k):
            if k < 0:
                return 0
            if r < 0 or c < 0 or r == m or c == n:
                return 1

            if dp[r][c][k] != -1:
                return dp[r][c][k]

            dp[r][c][k] = dfs(r-1,c,k-1) + dfs(r+1,c,k-1) + dfs(r,c-1,k-1) + dfs(r,c+1,k-1)
            return dp[r][c][k]

        return dfs(startRow, startColumn, maxMove) % (10 ** 9 + 7)

할 것

더 많은 문제를 해결하고 개념을 추출