I recently learned about matrix exponentiation for 1-dimensional dp states in which we determine a transition matrix M which is raised to a power to find the nth dp state. I attempted this problem — BBRICKS and figured out the dp state to be:-
dp[i][j] = No. of ways to place j bricks among the first i columns in a valid way, such that the ith column contains the last brick placed.
So the relation can be dp[i][j] = dp[i−1][j−1] + dp[i−2][j−1] + dp[i−1][j]
I was wondering how we can solve this using matrix exponentiation, now that my dp state is 2d. Can someone please explain a solution?
Thanks!
Your text to link here...
I read the blog but still can't figure out how to solve this problem. Can you help me?