Matrix Exponentiation for 2d DP recurrence

Правка en1, от akshatjain, 2018-10-30 19:41:33

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!

Теги matrix exponentiation, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский akshatjain 2018-10-30 19:41:33 705 Initial revision (published)