내 느낌상 DP를 통해서 구해야 하는 문제의 90% 이상은 조건을 만족하는 답의 갯수를 구하는 문제 또는 조건을 만족하면서 가장 작은 점수를 갖는 답의 점수를 찾는 문제이다.
조건을 만족하는 답의 갯수를 구하는 문제의 변형으로는, 조건을 만족하는 K번째의 답을 구하는 문제가 있다
조건을 만족하는 가장 작은 답의 점수를 찾는 문제의 변형으로는, 점수가 아닌 답 자체를 출력하게 하는 문제가 있다. 보통 역추적이라고 말하는 것.
그럼 나머지 10%는 뭐지.. 다른게 있긴 한가? 뭐가 더 있을것 같긴 한데 당장 떠오르지는 않아서 그냥 대충 90%라고 해두겠다
암튼.. 답의 갯수를 구하는 문제는 DP[i]= sum_j(f(dp[0], …, dp[j])) 대충 뭐 이런식으로 나온다. 그리고 특수한 식에 대해서는 dp값을 0부터 i까지 차례차례 전부 채워서 DP[i]를 구하는 대신에, 빠르게 계산할수 있다. 대표적으로, f가 선형일때에는 선형 점화식의 빠른 계산법을 사용할수 있다.
그리고 본론인, 최솟값을 구하는 문제는 DP[i]= min_j(f(dp[0], …, dp[j])) 대충 뭐 이런식으로 나오는 경우이다.