DP(Dynamic Programming) [동적 계획법]

🔍 특징

• 부분 문제의 정답을 저장하여 재활용

• 중복되는 계산을 피함 (시간 절약!)

• 탑다운(재귀) 또는 바텀업(반복) 방식으로 구현 가능

🎯 사용 조건

1. 최적 부분 구조
→ 큰 문제의 정답이 작은 문제의 정답으로 구성되는 경우

2. 중복 부분 문제
→ 동일한 작은 문제를 여러 번 반복해서 계산하는 경우

🧱 대표적인 구조

int[] dp = new int[n+1]; // 결과 저장용 배열

dp[0] = ...;  // 기본값
dp[1] = ...;

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2]; // 예시: 피보나치 구조
}

💡 예시: 2×n 타일 채우기 문제

• 문제: 가로 길이 n인 공간을 2×1 타일로 채우는 경우의 수

• 점화식:
dp[n] = dp[n-1] + dp[n-2]

• 의미:
• 마지막에 세로로 1개 놓으면 dp[n-1]
• 마지막에 가로로 2개 놓으면 dp[n-2]

📘 대표 문제들

• 피보나치 수열

• 계단 오르기

• 2×n 타일링

• 최장 공통 부분 수열 (LCS)

• 배낭 문제 (Knapsack)

🛠 구현 방식 비교