Matrix exponentiation for 2 Dimensional Recurrence

Revision en1, by Tobby_And_Friends, 2017-07-02 06:58:40

I was trying this problem from SPOJ: I figured out the recurrence for the problem which is f(x, y) = f(x — 1, y) + f(x, y — 1) + f(x — 1, y — 1), f(x, 0) = f(0, y) = 1. The constraints of the problem does not allow me to use normal DP and I'm not aware how to use matrix exponentiation technique for 2-D recurrence. I read this article: but I could not fully understand the idea. Any help is really appreciated.

Tags 2d-dp, #matrix exponentialtion


  Rev. Lang. By When Δ Comment
en1 English Tobby_And_Friends 2017-07-02 06:58:40 614 Initial revision (published)