Problem1496--递推-走格子

1496: 递推-走格子

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 32  Solved: 28
[Status] [Submit] [Creator:]

Description

在一无限大的二维平面中,我们做如下假设:
1、 每次只能移动一格;
2、 不能向后走(假设你的目的地是“向上”,那么你可以向左走,可以向右走,也可以向上走,但是不可以向下走);
3、 走过的格子立即塌陷无法再走第二次;
求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。

Input

仅一个数n(2<=n<=20),为要走的步数。

Output

输出仅一个数,为方案数。

Sample Input Copy

6

Sample Output Copy

239

Source/Category

 提高C