How to convert a dynamic programming problem to a binary exponentiation problem ?

Revision en1, by ghoshsai5000, 2017-04-06 10:08:10

I did my first dynamic programming problem successfully today here The editorial says that it can be solved int (log n) time with binary exponentiation of a 2x2 matrix. Can someone tell me how to convert a dynamic programming problem into a binary exponentiation problem ?

I don't want code. I want to practice the coding and implementation part myself. I want to know how to get the matrix from the recursive equations.

Let f(X, n) represent the number of paths ending in D with n moves left if the ant is at vertex X.

Then, f(D, 0) = 1, f(A/B/C, 0) = 0

Also, f(D, n) = 3f(A/B/C, n-1) f(A/B/C, n) = f(D, n-1) + 2f(A/B/C, n — 1)

How can I convert these equations into a matrix which needs to be exponentiated ?

Tags binary expone, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ghoshsai5000 2017-04-06 10:08:10 889 Initial revision (published)