I recently came across matrix-related ideas for solving DP problems, and I would like to discuss the same.
Problem Statement
Let's say we have a DP problem where we have a 2-Dimensional DP array say DP[N][K] (N rows K columns, K is small) where the DP[N] row denotes the base cases, and DP[0] row denotes the final DP values which we are interested.
Let's say the transitions between the DP rows are already predefined, (i.e.) the relation between Dp[i] and Dp[i+1] is known.
- For example: $$$dp[i][0] = dp[i+1][1] + 2 * dp[i+1][2]$$$
Now the problem is, given Q queries, for each query, we can modify the transitions between any two adjacent rows Dp[i] to Dp[i+1] , After performing each query, We should recalculate the final values of Dp[0] th row after performing each query. Assume that the transitions are in linear combination of next row of Dp.
Solution Idea:
- This problem may seem hard, because changing a transition in the middle row of dp table, would change a lot of values in the dp table, which would be hard to recalculate faster. And also the change in one transition affects many entries of DP table and there is no obviuos pattern which could be observed on DP values with respect to these changes.
- We shall think on some new ways to represent these DP Transitions, and Matrices comes to rescue.
- The idea of the solution is based on Matrix Exponentiation where we represent the transitions between Dp[i] and Dp[i+1] in a $$$K * K$$$ matrix.
- Now the final Dp values is the product of all N matrices.
- So for every query, we need to change a matrix at $$$i^{th}$$$ position, and recalculate the product of all matrices.
- This can be done with the help of Segment-Tree where we maintain a $$$K * K$$$ matrix in each node representing the product of matrices covered by the segment. Every change in transition is a point update and the root node of Segment Tree reveals the final Dp values which we are interested in.
- The overall time complexity is $$$O(K^3Nlog(N))$$$
