Give a rectangle of width W and height 2*H-1.How many ways we can fill the rectangle with 1 x H tiles?
How to find reccurence relation for this type of problems.(This problems is from Topcoder TCO 2014)
Example :H=2 W=4 Ans=11
W must be multiple of H else the answer is 0.
consider the 2*H-1 dimension as line:
- size of a domino tile in that one line is either 1 or H
- there can fit only one H sized piece in that line
- next (H-1) lines must have 1s on the exact places as this line
Can you piece it together now or should I go on?