Hust oj 1929 走三方，路迢迢水长长（递推）

从原点出发，一步只能向右走、向上走或向左走，每一步都只能走一个单位长度。恰好走N步且不经过已走的点共有多少种走法？

输出走法个数并换行。

1

3 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;long long int a[20];
int n;
void init()
{a[1] = 3;a[2] = 7;for(int i=3;i<20;i++){a[i] = a[i-1] * 2 + a[i-2];}
}int main()
{init();while(~scanf("%d",&n)){printf("%lld\n",a[n]);}
}