Блог пользователя akshatjain

Автор akshatjain, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится