DP (다이나믹 프로그래밍)

다이나믹 프로그래밍 

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기

 

 

예제 - 백준 2 X n 타일링 (11726)

#include <bits/stdc++.h>
using namespace std;

int d[10005];
int mod = 10007;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  d[1] = 1;
  d[2] = 2;
  for(int i = 3; i <= n; i++) d[i] = (d[i-1]+d[i-2])%mod;
  cout << d[n];
}

 

 

결론

dp는 문제를 잘 파악해서 테이블과 점화식을 잘 설정하는 것이 키 포인트...!

문제 유형이 다양하기 때문에 최대한 많이 풀어보기

 

 

참고 - https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?page=2