http://www.algorithmist.com/index.php/UVa_10918The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.I only want to know how these recurrence relations came:f(n)=f(n-2)+2*g(n-1)g(n)=f(n-1)+g(n-2)where f(n)=number of tilings of a 3xN rectangleg(n)= number of tilings of a 3xN rectangle with one of its corner squares removed
Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?
recurrence relation;dynamic programming;correctness proof
Suppose that the rectangle to be tiled has 3 rows and $n$ columns. Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options:All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$.Exactly one tile touching the $n$th column is vertical. It can either touch the top or the bottom. For each of these two options, if you remove it then you get a tiling of a rectangle of size $3\times (n-1)$ with one corner square added. That square must be tiled by a horizontal tile, after whose removal you are left with a tiling of a $3\times(n-1)$ rectangle with one corner square removed.This explains the formula $f(n) = f(n-2) + 2g(n-1)$.The same sort of analysis yields the formula for $g(n)$, but I leave that one for you.