DP개념정리

정의

simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. (Wikipedia)

sub-problem이란 무엇인가? 점화식(recursion)에서 현재값을 계산하기 위해 참조하는 다른 문제를 sub-problem이라고 한다. 이러한 sub-problem을 따라가다보면 더이상 분해할 필요 없이 계산가능한 작은 문제(base case)가 나오며, 전체 노드와 의존성을 그래프로 표현해보면 반드시 DAG형태이다. 즉 partial ordering이 존재한다.

기본적인 DP풀이과정

점화식 발견 및 완전탐색 구현

Memoization이 가능하려면 재귀함수는 순수함수여야 한다. 아니라면 외부환경에 따라 값이 달라진다는 의미이므로 값을 저장할 수가 없다. 본인이 설계한 재귀함수가 순수함수가 아니라면 순수함수가 될 때 까지 의존하는 변수를 함수인자로 포함시켜 순수함수로 만들자.
다양한 점화식이 가능하며, 단순히 방향만 다른 점화식일 수도 있지만 결과값 정의부터 완전하게 다른 두 점화식이 있을 수도 있다. 문제에 따라 적절한 점화식을 찾는 능력은 많은 연습으로만 얻을 수 있음. (ex: boj.kr/15773은 [x,n)풍선남았고 현재 y고도일때 터트리기최대개수z를 묻는데, f(x,y)=z로 두면 최적화가 거의 힘들고, [0,x]풍선으로 z개터트릴때 최소고도y로 약간 비틀어서 f(x,z)=y로 정의하면 점화식이 더 예쁘게 나와서 풀 수 있다.)

상태표현 개선

점화식에서 필요없는 인자를 가능한 많이 제거(다른 매개변수로부터 추출가능하거나, 그리디한 어떤 성질에 의해 이런 인자 없이도 구할 수 있다거나 등)
값 대신 인덱스 저장(KOI 경찰차)
동일한 결과를 내는 다른 점화식 찾기(dp의 반환값 정의 개선 등)(1번 참고)

상태전이 개선

현재노드의 의존성(의존하는 dp값)의 개수가 많다면? Bottom Up으로 짜면 자료구조에 잘 저장해서 관리해주면 bulk로 가져올 수 있다. (ex: 연속된 작은문제들에 대한 쿼리(합, min 등)를 Segment Tree, Prefix Sum 같은거로 구하기 등)
Sliding Window 혹은 Toggling이라고 불리는 기법을 적용하면 공간복잡도도 마찬가지로 더 줄일 여지가 있다.
dp결과타입이 bool형태일때

true일때 스킵 false일때 뭔가 뿌려주는 형태라면, bottom up으로 현재dp값을 의존하는 노드들에 뿌려주는 형태로 짜면 sieve처럼 최적화 될 수 있다. 가끔 게임이론DP같은거에 등장. (BOJ16888)
bitset 가능한 경우가 종종 있다. 예를들어 $f(x,y) = f(x-1,y+1)|f(x-1, y-1)$이면 $f(x)=f(x-1)<<1|f(x-1)>>1$ 처럼 bitset연산으로 최적화 가능.
f(x,y,z)에서 x,y고정시키고 true가 되는 z를 살펴봤을때 그게 연속한다면 f1(x,y) = f(x,y,z)가 true인 최소z, f2(x,y) = f(x,y,z)가 true인 최대z로 정의해서 인자 생략가능(KOI2019 검은돌)

알려진 DP최적화기법 적용 가능한지 체크(볼록성, Monge, Opt위치단조성 등)

TopDown vs Bottom-up

올바른 점화식은 항상 DAG이다. 그래서 항상 위상정렬이 가능하고, 점화식을 재귀함수로 그대로 작성하면 알아서 위상정렬된 순서(dfs로 구현한 위상정렬과 같음)대로 계산된다. 이게 Top-down DP이다. Bottom-up DP는 재귀함수로 위상정렬을 하지 않기 때문에 처음에는 DP Table만 존재한다. 거기에 프로그래머가 올바른 위치에 초기값을 추가(base case)하고 적절한 순서(올바른 위상순서)대로 테이블을 계산하도록 주의하여 코딩해야 한다. 명시적인 위상정렬 없이 루프문 순서만 잘 조정해줘도 되는 경우가 많이 있다. O(V+E)~O(V^2)인 위상정렬이 없어도 되므로 의존성 개수가 많은 DP의 경우 Bottom-up으로 상태전이를 최적화할 여지('기본적인 DP풀이과정' 4번 참고)가 있다.