I am having problems understanding what exactly is going on in the solve function below. I see what it does, however it still is unclear to me - I cannot visualize it, or just get myself to understand it. Can someone explain it?
Original problem statement (2663 -- Tri Tiling):
In how many ways can you tile a 3xn rectangle with 2x1 dominoes?
Here is a sample tiling of a 3x12 rectangle.
#include <stdio.h>
int dp[32];
int solve(int n)
{
if(dp[n]!=-1)
return dp[n];
else
{
int i;
int res = 3*solve(n-2);
for(i=4;i<=n;i+=2)
res+=2*solve(n-i);
return dp[n]=res;
}
}
int main()
{
int i;
for(i=0;i<32;i+=2)
dp[i]=-1;
for(i=1;i<32;i+=2)
dp[i]=0;
dp[0]=1;
scanf("%d",&i);
while(i!=-1)
{
printf("%d\n",solve(i));
scanf("%d",&i);
}
return 0;
}