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.
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
