1차원 DP — 점화식 세우기

겹치는 작은 문제를 한 번만 풀고 저장해요. `dp[i]`를 앞 값들로 표현하면 절반은 끝나요.

이럴 때 써요

같은 계산을 여러 번 반복하게 되고, 그 결과를 재활용할 수 있을 때
n번째 답이 n-1, n-2번째 답으로 표현되는 문제 (계단 오르기, 피보나치, 집 털기)
완전 탐색으로 풀면 시간이 터지는데, 부분 문제가 계속 겹쳐 보일 때
선택의 순간마다 이걸 고른다 / 안 고른다로 갈리고, 앞 결과가 뒤에 그대로 쓰일 때

개념

DP는 큰 문제를 작은 문제로 쪼개서, 작은 문제의 답을 한 번만 구하고 저장해 두는 거예요. 두 조건이 맞으면 통해요. 최적 부분 구조 — 큰 문제의 답이 작은 문제의 답으로 만들어져요. 겹치는 부분 문제 — 같은 작은 문제를 여러 번 다시 풀게 돼요. 이 겹침을 저장으로 없애는 게 핵심이에요.

점화식 세우는 순서

상태 정의 — dp[i]가 정확히 무슨 값인지 한 문장으로 못 박아요. 여기서 애매하면 뒤가 다 흔들려요.
점화식 — dp[i]를 dp[i-1], dp[i-2] 같은 앞 값으로 표현해요.
초기값(base case) — 점화식이 닿지 못하는 맨 앞 몇 칸을 직접 채워요.
답 위치 — 최종 답이 dp[n]인지 dp 전체의 최댓값인지 정해요.

계단 오르기로 감을 잡아요. 한 번에 1칸 또는 2칸 오를 때, n번째 칸에 서는 방법의 수는? 마지막 걸음이 1칸이었다면 그 전엔 n-1에, 2칸이었다면 n-2에 있었어요. 그래서 dp[i] = dp[i-1] + dp[i-2]. 이게 피보나치와 똑같은 모양이에요.

"계단 5칸, dp[i] = dp[i-1] + dp[i-2]"
dp[0] = 1   (시작점, 방법 1가지로 둬요)
dp[1] = 1   (1칸 오르기 한 가지)
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
dp = [1, 1, 2, 3, 5, 8]
답: dp[5] = 8

채우는 방향은 두 가지예요. 탑다운(메모이제이션) 은 solve(n)을 재귀로 부르되, 이미 푼 값은 캐시에서 꺼내 써요. 문제를 위에서 아래로 쪼개 내려가요. 바텀업(타뷸레이션) 은 작은 칸부터 큰 칸으로 반복문을 돌며 dp 배열을 순서대로 채워요. 둘 다 답은 같고, 재귀 깊이가 걱정되면 바텀업이 안전해요.

방식	방향	채우는 법	주의점
탑다운	위 → 아래	재귀 + 캐시	캐시 조회·저장을 빼먹으면 지수 시간
바텀업	아래 → 위	반복문으로 순서대로	작은 칸부터 채워야 참조가 유효해요

패턴 코드

탑다운 — 재귀 + 캐시(메모이제이션)캐시에 있으면 바로 반환하고, 없으면 계산한 뒤 반드시 저장해요. 이 두 줄이 지수 시간을 O(n)으로 바꿔요.

javascript
Copy code
function climbStairs(n) {
  const memo = new Map();
  function solve(i) {
    if (i <= 1) return 1; // base case: 0칸·1칸
    if (memo.has(i)) return memo.get(i); // 캐시 조회
    const result = solve(i - 1) + solve(i - 2);
    memo.set(i, result); // 캐시 저장
    return result;
  }
  return solve(n);
}

바텀업 — 반복문으로 dp 배열 채우기(타뷸레이션)초기값 dp[0], dp[1]을 먼저 두고, 작은 칸부터 순서대로 채워요. 답은 dp[n]이에요.

javascript
Copy code
function climbStairs(n) {
  if (n <= 1) return 1;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

이 유형으로 풀어보기

← 유니온 파인드 — 그룹·사이클 판정 배낭 문제 →