How to solve linear recurrences involving two functions?
Posted
by
Aditya Bahuguna
on Programmers
See other posts from Programmers
or by Aditya Bahuguna
Published on 2014-06-06T15:51:22Z
Indexed on
2014/06/06
21:49 UTC
Read the original article
Hit count: 241
Actually I came across a question in Dynamic Programming where we need to find the number of ways to tile a 2 X N area with tiles of given dimensions.. Here is the problem statement
Now after a bit of recurrence solving I came out with these.
F(n) = F(n-1) + F(n-2) + 2G(n-1), and
G(n) = G(n-1) + F(n-1)
I know how to solve LR model where one function is there.For large N as is the case in the above problem we can do the matrix exponentiation and achieve O(k^3log(N)) time where k is the minimum number such that for all k>m F(n) does not depend on F(n-k). The method of solving linear recurrence with matrix exponentiation as it is given in that blog.
Now for the LR involving two functions can anyone suggest an approach feasible enough for large N.
© Programmers or respective owner