C语言，wave

C语言，wave 题目描述

一个n列的网格，从(0,0)网格点出发，波形存在平波(从(x,y)到(x+1,y))，上升波(从(x,y)到(x+1,y+1))，下降波(从(x,y)到(x+1,y−1))三种波形，请问从(0,0)出发，最终到达(n,0)的不同波形有多少种？如图，3列网格有7种不同的波形。

输入

第一行是样例数T(1≤T≤42)。 以后每行一个整数n(1≤n≤42)。

输出

每行输出一个样例的结果。

样例输入

3
1
2
3

样例输出

1
3
7

 从一格到下一格有三种可能性，终点前一格到达终点格有3种可能性

 

 重新排列一下

#include 
long long num[45][45];
void result()
{
    int i,j;
    num[1][1]=1,num[1][2]=1,num[1][3]=1;
    for(i = 2;i < 44;i++)
    {
        num[i][1] = 1;
        num[i][2*i+1] = 1;
        num[i][2] = num[i-1][1]+num[i-1][2];
        num[i][2*i] = num[i-1][2*i-1]+num[i-1][2*i-2];
        for(j = 3;j <= 2*i-1;j++)
        {
            num[i][j] = num[i-1][j-2]+num[i-1][j-1]+num[i-1][j];
        }
    }
}
int main() 
{
    result();
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%lldn",num[n][n+1]);
    }
	return 0;
}