贴瓷砖（动态规划）

 关键：找出递推公式

如图

两列有3种贴法，前面n-2列的贴法乘上后2列的贴法，即3*dp[n-2]，

4列有2种贴法，就有2*dp[n-4]

同理有2*dp[n-6]，2*dp[n-8]...

所以dp[n]=3*dp[n-2]+2*dp[n-4]+2*dp[n-6]+...

dp[n-2]=3*dp[n-4]+2*dp[n-6]+2*dp[n-8]+...

两式作差，有dp[n]-dp[n-2]=3*dp[n-2]-dp[n-4]

即dp[n]=4*dp[n-2]-dp[n-4]

（由于有乘积关系，故临界值dp[0]应为1）

#include <stdio.h>
#include <string.h>
int main()
{int n,pd[31];memset(pd,0,sizeof(pd));pd[0]=1;pd[2]=3;for(int i=4;i<31;i+=2) pd[i]=4*pd[i-2]-pd[i-4];while(1){scanf("%d",&n);if(n==-1) break;else printf("%d\n",pd[n]);}return 0;
}