分两种情况，如果向上的话就有三种走法，一种向上，一种向左，一种向右，如果是向左（右）走，就有两种走法，一种向上，一种向左（右），然后继续分方向讨论……用一个二维数组，一个存储向上方向的步数，一个存储另外两个方向的步数，最后求和就可以了……
#include "stdio.h"
int main()
{
int T,n;
__int64 s[2][32]={1,0};
int i;
for(i=1;i<=30;i++)
{
s[0][i]=s[0][i-1]+s[1][i-1];
s[1][i]=2*s[0][i-1]+s[1][i-1];
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%I64d\n",s[0][n]+s[1][n]);
}
return 0;
}