동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제의 답으로 표현하고, 같은 계산을 반복하지 않도록 저장하면서 푸는 방식입니다.
- 큰 문제의 답을 작은 문제들의 답으로 만든다.
- 같은 계산을 여러 번 하지 않는다.
- 점화식이 보일 때
- 같은 상태를 반복 계산할 때
- 최적값, 경우의 수, 최소/최대 문제일 때
- 상태를 어떻게 정의할 것인가
- 점화식이 무엇인가
- 초기값이 무엇인가
- 메모이제이션과 바텀업 중 뭐가 더 자연스러운가
dp = [0] * (n + 1) # -> 1차원 DP 테이블
dp[0] = 1 # -> 초기값 예시from functools import lru_cache
@lru_cache(None)
def f(x: int) -> int:
return 0 # -> 메모이제이션 예시- 상태 정의가 애매한 것
- 초기값을 잘못 두는 것
- 그리디로 풀 수 있는 문제를 DP로 과하게 푸는 것
- 같은 상태를 반복 계산하면 DP를 의심한다.