생각 순서
- 상태 정의 (
dp[i]= …) - 점화식
- 기저
- 반복 순서 (작은 것 → 큰 것)
예: 계단
dp[i] = dp[i-1] + dp[i-2]
함정
상태 차원을 너무 키우기, 점화 방향 반대.
한 줄
> 상태 · 점화 · 기저 · 순서.
동적 계획법 입문
부분 문제 답을 표에 저장해 중복 계산을 없앱니다.
부분 문제 답을 표에 저장해 중복 계산을 없앱니다.
dp[i] = …)dp[i] = dp[i-1] + dp[i-2]
상태 차원을 너무 키우기, 점화 방향 반대.
> 상태 · 점화 · 기저 · 순서.