http://acm.hdu.edu.cn/showproblem.php?pid=2501

题解：递推

dp[i+2]=dp[i+1]+2*dp[i]

dp[i+2]相对于dp[i]正好多一个2x2的正方形,当前 i+1 个格子都填满后,则第i+2 个格子就确定了,而当前i个 都填满后,为了不与i+1 个格子都填满的方案重复,则还有两种方案可选,直接填2x2或填两个1x2(横着填)

#include <iostream>
#include <stdio.h>

using namespace std;
int n,t;
int dp[45];
int main()
{   dp[0]=1;
    dp[1]=1;
    dp[2]=3;
        for(int i=3;i<=40;i++){
            dp[i]=dp[i-1]+2*dp[i-2];
        }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d\n",dp[n]);

    }
    //cout << "Hello world!" << endl;
    return 0;
}