10. 다이나믹 프로그래밍

다이나믹 프로그래밍

빠른 설명

다이나믹 프로그래밍(DP)은 같은 부분 문제를 반복해서 풀지 않도록 값을 저장해 두는 방법이다. 점화식과 초기값이 핵심이다.

언제 쓰는가

• 현재 답이 이전 답들로 표현될 때
• 같은 상태를 여러 번 계산하게 될 때
• 최댓값, 최솟값, 경우의 수를 누적해서 구할 때

시간복잡도

• 보통 상태 수 × 상태 하나를 계산하는 비용
• 예: 피보나치 DP는 $O(N)$

참고자료

• CP-Algorithms - Introduction to Dynamic Programming
• Wikipedia - Dynamic programming
• USACO Guide - Intro to DP
• GeeksforGeeks - Dynamic Programming

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    int n = 10;
    vector<long long> dp(n + 1);
 
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
 
    cout << dp[n] << '\n';
}

Python 코드

n = 10
dp = [0] * (n + 1)
 
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
 
print(dp[n])