Matrix DP
DP 문제를 풀 때, 점화식을 써보고 해당 점화식이 Linear한 1차 다항식이면 Matrix DP가 가능하다.
Matrix DP의 최고 장점은 분할정복이 가능하다는 점이다. 예를 들면 행렬 A의 200승은 A의 100승 두 개의 곱으로 구할 수 있다.
예제
https://www.acmicpc.net/problem/13250
주사위 게임이라는 문제인데, 문제를 잘 읽어보면 아래와 같은 점화식으로 정리 가능하다.
D(n) = 1 + ( D(n-1) + D(n-2) + D(n-3) + D(n-4) + D(n-5) + D(n-6) )
자 그럼 행렬 점화식으로 바꿔보자. 행렬 점화식이 성립하려면 좌변과 우변이 X(n) 과 X(n-1) 형태로 표현되어야 한다. 아래 그림과 같이 표현된다고 가정해보자. C는 상수항이다.
n-1 부터 n-5까지와 상수항은 우변에 있는 것을 그대로 사용할 수 있도록 1을 적절한 위치에 넣어주자.
이제 맨 첫줄만 채우면 된다. 맨 첫줄은 앞서 구한 점화식의 각 항의 계수를 넣어주면 끝난다.
