DP (동적 계획법)

계단 4칸을 한 번에 1칸 또는 2칸씩 올라가는 방법이 몇 가지인지 세어 봅니다. dp[i]는 "i번 칸까지 오는 방법 수"입니다.

2번, 3번 칸은 직접 세어 봐도 값이 맞습니다. 4번 칸부터는 손으로 세기 번거롭지만, 규칙이 확인되었으니 그냥 더하면 됩니다.

이 표가 DP의 전부입니다. 마지막 한 걸음을 무엇으로 밟았는지로 경우를 나눴더니(1칸이었다면 3번에서 왔고, 2칸이었다면 2번에서 왔습니다), 큰 문제가 이미 풀어 둔 작은 문제 두 개로 쪼개졌습니다.

DP 문제는 다음 네 단계로 사고합니다. 코드보다 이 순서가 중요합니다.

1. 상태 정의 — dp[i]가 "무엇"인지 한 문장으로 적습니다. 이것이 흔들리면 나머지가 전부 흔들립니다.

// dp[i] = i번째 계단까지 오는 방법의 수
// (다른 예: dp[i] = i원을 만드는 최소 동전 수)
const dp: number[] = [];

2. 점화식 — 마지막 선택 하나를 고정해 봅니다. "마지막에 1칸 뛰었다면? 2칸 뛰었다면?"

dp[i] = dp[i - 1] + dp[i - 2];

3. 기저 사례 — 더 쪼갤 수 없는 시작값을 정합니다.

dp[0] = 1;
dp[1] = 1;

4. 채우는 순서 — 참조하는 값이 먼저 계산되도록 돕니다(보통 작은 쪽에서 큰 쪽으로).

for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

전체 코드 — 계단 오르는 방법의 수:

function solution(n: number): number {
  // 1단계: dp[i] = i번 칸까지 오는 방법 수
  const dp = Array(n + 1).fill(0);
  // 3단계: 기저 사례
  dp[0] = 1;
  if (n >= 1) dp[1] = 1;
  // 4단계: 작은 칸부터 채우면 2단계의 점화식이 항상 성립
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

• "방법의 수", "최솟값/최댓값", "가능한가" 를 묻고, 답에 이르는 과정이 선택의 연속이면 DP를 의심합니다.
• 완전탐색으로 짜면 지수 시간인데, 자세히 보면 같은 상황을 여러 번 다시 계산하고 있을 때가 결정적 신호입니다. 그 "상황"이 곧 상태입니다.
• 제약이 N ≤ 1,000 또는 N ≤ 100,000이면서 그리디로는 반례가 나오면 대개 DP입니다.
• 대표 상황: 계단·타일 채우기(경우의 수), 동전 거스름돈(최소 개수), 배낭 담기(최대 가치), 격자 경로, 문자열 편집 거리, 연속 부분합.

// 대표 패턴 1 — 계단 오르기 (경우의 수)
const dp = [1, 1];
for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

// 대표 패턴 2 — 동전 최소 개수 (최적화)
const dp = Array(target + 1).fill(Infinity);
dp[0] = 0;
for (let amount = 1; amount <= target; amount++)
  for (const coin of coins)
    if (coin <= amount) dp[amount] = Math.min(dp[amount], dp[amount - coin] + 1);

// 대표 패턴 3 — 0-1 배낭 (고르거나 말거나)
const dp = Array(budget + 1).fill(0);
for (let i = 0; i < n; i++)
  for (let w = budget; w >= cost[i]; w--)   // 역순! — 같은 물건 중복 방지
    dp[w] = Math.max(dp[w], dp[w - cost[i]] + value[i]);

2차원으로 넘어가면 격자 경로가 전형입니다 — dp[r][c] = dp[r-1][c] + dp[r][c-1]이고 가장자리는 1입니다. 상태가 좌표 두 개로 늘었을 뿐 사고 순서는 같습니다.

• 상태 정의가 모호한 채 점화식부터 찾음 — "dp[i]는 정확히 무엇인가"를 먼저 문장으로 적으세요.
• 0-1 배낭의 안쪽 루프를 정순으로 돌림 — 같은 물건을 여러 번 담게 됩니다(완전 배낭과의 차이).

for (let w = cost[i]; w <= budget; w++)     // 잘못 — i번 물건을 중복해서 담음
  dp[w] = Math.max(dp[w], dp[w - cost[i]] + value[i]);

for (let w = budget; w >= cost[i]; w--)     // 고침 — 아직 갱신 안 된 값만 참조
  dp[w] = Math.max(dp[w], dp[w - cost[i]] + value[i]);

• 기저 사례 누락·오류 — dp[0]이 틀리면 전부 틀립니다. 최솟값 문제는 초기값을 Infinity로 둡니다.
• max/min 문제에서 "불가능" 상태(Infinity)를 답에 그대로 더함 — 가능 여부를 확인한 뒤 사용합니다.

dp[i] = dp[i - coin] + 1;                           // 잘못 — Infinity + 1을 답으로 씀
if (dp[i - coin] !== Infinity) dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 고침

• Kadane류(연속 부분합)에서 음수 전체 배열 처리 누락 — 답이 0이 되어 버립니다.

• 필요한 것은 딱 두 가지입니다. 점화식(dp[i]를 더 작은 dp들로 표현하는 관계식)과 기저 사례(더 쪼갤 수 없는 시작값). 나머지는 이 둘을 코드로 옮기는 작업일 뿐입니다.
• DP가 성립하는 조건: 큰 문제의 최적해가 작은 문제의 최적해로 이루어져야 하고(최적 부분 구조), 작은 문제들이 서로 겹쳐야 합니다(중복 부분 문제). 겹치지 않으면 그냥 분할 정복이고, 최적 부분 구조가 없으면 DP로 풀리지 않습니다.
• 탑다운 vs 바텀업: 재귀에 메모 배열을 붙이는 탑다운은 점화식을 그대로 옮길 수 있어 사고가 쉽고, 필요한 상태만 계산합니다. 반복문으로 채우는 바텀업은 호출 비용과 스택 깊이 문제가 없어 빠릅니다. 상태가 100만 개를 넘으면 바텀업 쪽이 안전합니다.
• 복잡도 계산법: (상태의 개수) × (한 상태를 계산하는 비용)입니다. 배낭이 O(N × 예산)인 것도, 격자 경로가 O(행 × 열)인 것도 이 곱입니다. 이 값이 제한을 넘으면 상태를 줄이거나(차원 축소) 전이를 줄여야(자료구조로 최댓값 조회) 합니다.
• 공간 최적화: 점화식이 직전 한두 줄만 참조하면 2차원 배열 대신 1차원 배열 하나를 덮어쓰며 재사용할 수 있습니다. 0-1 배낭의 역순 루프가 바로 이 최적화의 결과이고, 역순이 필요한 이유도 여기에 있습니다.

시각화로 "작은 답 → 큰 답" 조립을 본 뒤, 계단(1D) → 동전/배낭 → 격자 경로(2D) → Kadane 변형 순으로. DP는 이 사이트에서 문제가 가장 많은 상급 유형이며, 상태 정의 연습이 전부입니다.