복잡한 문제를 작은 하위 문제들로 나눠서 푸는 알고리즘 기법이에요.
같은 계산을 반복하지 않도록 중간 결과를 저장해서 다시 활용하는 게 핵심입니다.
다음 두 가지 조건을 만족할 때 DP를 사용할 수 있어요:
Overlapping Subproblems (부분 문제가 반복됨)
→ 같은 계산을 여러 번 반복하게 됨
예: 피보나치 수열
Optimal Substructure (최적 부분 구조)
→ 큰 문제의 정답이 작은 문제의 정답들로 구성됨
예: "현재까지 최선의 선택을 누적하면 전체에서 최선이 됨
요소 | 설명 |
---|---|
상태(state) | 어떤 기준으로 문제를 나눌 것인지 정의 (보통 인덱스 등) |
점화식(transition) | 이전 상태들로 현재 상태를 계산하는 규칙 |
초기값(base case) | 가장 작은 문제들의 정답을 지정 |
저장공간(dp 배열) | 각 상태별 결과를 저장 (중복 계산 방지) |
// F(n) = F(n-1) + F(n-2)
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
구성 요소 | 내용 |
---|---|
상태 | dp[i] : i번째 인덱스부터 끝까지 발음 가능한 경우의 수 |
점화식 | dp[i] = dp[j] 들의 합 (i ~ j 구간이 유효한 음인 경우) |
초기값 | dp[len] = 1 (문자열 끝에 도달한 경우 = 성공적인 분할) |
저장공간 | int[] dp = new int[len + 1]; (메모이제이션용) |