이전 편에서 dp[i]에 무엇을 저장할지 정의했다. 이제 dp[i]를 어떻게 계산할지 결정해야 한다. 이것이 점화식이다.
점화식이란
점화식은 dp[i]를 이전 dp 값들로 표현하는 수식이다.
피보나치의 점화식은 dp[i] = dp[i-1] + dp[i-2]였다. dp[i]를 dp[i-1]과 dp[i-2]로 표현한다.
점화식을 세우려면 한 가지를 물어보면 된다. "마지막으로 어떤 결정을 내렸는가?"
마지막 결정으로 경우 나누기
동전 교환 문제에서 dp[i] = 금액 i원을 만드는 최소 동전 수.
"i원을 만들기 위한 마지막 결정"은? 마지막에 동전 하나를 추가하는 것이다. 추가한 동전의 종류에 따라 경우를 나눌 수 있다.
마지막에 1원짜리를 넣었다면 → 나머지는 (i-1)원을 만들어야 함 → dp[i-1] + 1
마지막에 5원짜리를 넣었다면 → 나머지는 (i-5)원을 만들어야 함 → dp[i-5] + 1
마지막에 10원짜리를 넣었다면 → 나머지는 (i-10)원을 만들어야 함 → dp[i-10] + 1이 중 최솟값이 dp[i]다.
dp[i] = min(dp[i-1], dp[i-5], dp[i-10]) + 1일반화하면:
dp[i] = min(dp[i - c] + 1) for all c in coins, where i >= c코드로 표현
for (int i = 1; i <= target; i++) {
for (int c : coins) {
if (i >= c && dp[i - c] != INF) {
dp[i] = Math.min(dp[i], dp[i - c] + 1);
}
}
}- 동전 종류마다 시도해보고 최솟값 갱신
i >= c: 동전이 목표 금액보다 크면 사용 불가dp[i - c] != INF:i-c원을 만들 수 없는 경우는 고려하지 않음
점화식을 세울 때 자주 쓰는 패턴
경우를 나눠서 최솟값 또는 최댓값을 취하는 패턴이 가장 많다.
- 최솟값 :
dp[i] = min(dp[j] + 비용)— 동전 교환, 최단 경로 - 최댓값 :
dp[i] = max(dp[j] + 가치)— 배낭, 최대 수익 - 경우의 수 :
dp[i] = sum(dp[j])— 계단 오르기, 타일링
flowchart LR
A["마지막 결정\n경우 나누기"] --> B["각 경우에서\ndp[이전상태] + 비용"]
B --> C["min/max/sum\n중 하나 선택"]
C --> D["점화식 완성"]
"마지막 결정"을 기준으로 경우를 나누고, 각 경우의 비용을 합산하거나 비교하면 점화식이 나온다.
점화식이 안 떠오를 때
작은 예시를 손으로 계산해보자. dp[3], dp[4], dp[5]를 직접 구하다 보면 패턴이 보인다. 그 패턴을 일반화하면 점화식이 된다.