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 statementNow after a bit of recurrence solving I came out with these.F(n) = F(n-1) + F(n-2) + 2G(n-1), andG(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.
How to solve linear recurrences involving two functions?
c++;algorithms;dynamic programming