akshatjain's blog

By akshatjain, history, 6 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I read the blog but still can't figure out how to solve this problem. Can you help me?