link- https://www.spoj.com/problems/M3TILE/
how to find the recurrence relation for this??
How to solve this problem?
Here is a hint…now try to think of the relation urself…if u further need help…then reply again
An = No. of ways to completely fill a 3 x n board. (We need to find this)
Bn = No. of ways to fill a 3 x n board with top corner in last column not filled.
Cn = No. of ways to fill a 3 x n board with bottom corner in last column not filled.
1 Like
Thank you for the explanation. Even though the explanation was pretty good and helped me to visualize the problem, I am still unable to come up with the relation (basically base cases). Please help me find them.
Final Recursive Relations are:
A[n] = A[n-2] + 2*(B[n-1])
Term b is multiplied to 2 because b and c are the same.
For calculating B[n]:
B[n] = A[n-1] + B[n-2]
Base Cases:
A0 = 1 A1 = 0
B0 = 0 B1 = 1
1 Like
Sir I thought in the same way.
I thought A(0)=0 A(1)=1
B(n)= if(n&1) return 1;
else return 0;
Is it correct??
Also can you please do the dry run for n=4