1. DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 경우

✅ 다이나믹 프로그래밍이란?

복잡한 문제를 작은 하위 문제들로 나눠서 푸는 알고리즘 기법이에요.

같은 계산을 반복하지 않도록 중간 결과를 저장해서 다시 활용하는 게 핵심입니다.


✅ 언제 쓰면 좋을까?

다음 두 가지 조건을 만족할 때 DP를 사용할 수 있어요:

  1. Overlapping Subproblems (부분 문제가 반복됨)

    → 같은 계산을 여러 번 반복하게 됨

    예: 피보나치 수열

  2. Optimal Substructure (최적 부분 구조)

    → 큰 문제의 정답이 작은 문제의 정답들로 구성됨

    예: "현재까지 최선의 선택을 누적하면 전체에서 최선이 됨


✅ DP의 핵심 구성 요소

요소 설명
상태(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 구성 (발음 경우의 수)

구성 요소 내용
상태 dp[i]: i번째 인덱스부터 끝까지 발음 가능한 경우의 수
점화식 dp[i] = dp[j]들의 합 (i ~ j 구간이 유효한 음인 경우)
초기값 dp[len] = 1 (문자열 끝에 도달한 경우 = 성공적인 분할)
저장공간 int[] dp = new int[len + 1]; (메모이제이션용)