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: http://www.spoj.com/problems/LVADER/en/. 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: https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation but I could not fully understand the idea. Any help is really appreciated.

#### History

Revisions

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