Actually I came across a question in Dynamic Programming where we need to find t

Question

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.

Explanation / Answer

Same method works: find a matrix that translates (F(n-1) F(n-2) G(n-1)) into (F(n) F(n-1) G(n)). A ((1 1 2) (1 0 0) (1 0 1)) matrix would do it.

Explanation

That's how matrix-by-vector multiplication works. A first element of a resulting vector is an inner product of a first row and an initial vector:

1*F(n-1) + 1*F(n-2) + 2*G(n-1)
which according to recurrence is F(n). Same goes for the second and third.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.