Problem Description
在一无限大的二维平面中，我们做如下假设：
1、  每次只能移动一格；
2、  不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、  走过的格子立即塌陷无法再走第二次；

求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
Input
首先给出一个正整数C，表示有C组测试数据
接下来的C行，每行包含一个整数n (n<=20)，表示要走n步。
Output
请编程输出走n步的不同方案总数；
每组的输出占一行。
Sample Input

2
1
2

Sample Output

3
7

2、  不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；

应该是

2、  不能向下走（没有什么“假设”）

答案是：f(n) = f(n-2) + 2*f(n-1); f(0)=1, f(1)=3;

谢谢啊，我貌似有点眉目了。

能说一下你怎么能这样想出来的吗？有没有什么直接的方法？

能说一下你怎么能这样想出来的吗？
------ 你说清楚一点儿，“这样”是什么？是指“不能向下走”，还是“f(n) = f(n-2) + 2*f(n-1)”？

如果是前者，“不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）”和“f(1)=7”相矛盾；

如果是后者，
设向上方向有a个，左右方向有b个。
因为 1个向上方向的下一步可以产生1个向上方向+2个左右方向；1个左右方向的下一步可以产生1个向上方向+1个左右方向
即 a(n+1步) = a(n步) + b(n步);
   b(n+1步) = 2*a(n步) + b(n步);
能直接看出 f(n) = f(n-2) + 2*f(n-1) 吗？不能也没关系，继续
设在第n步时，向上方向有a个，左右方向有b个，总数为 a+b 个
则在第n+1步时，向上方向有a+b个，左右方向有2a+b个，总数为 3a+2b 个
则在第n+2步时，向上方向有3a+2b个，左右方向有4a+3b个，总数为 7a+5b 个
（7a+5b）就是 2*（3a+2b） + （a+b）呀，即 f(n) = 2*f(n-1) + f(n-2)。
当然，不求出这个公式也没关系，就用最上面的原始公式 a=a+b; b=2a+b 也一样迭代，复杂度也一样。

#include <stdio.h>
int main()
{
int nstep(int n,int na,int nb,int m)；
int n=1,na=1,nb=0,m;
 printf("step: " );
 scanf("%d",&m);
 if(m>20) return 0;
 printf("number: %d\n",nstep(n,na,nb,m));
 return 1;   
}
int nstep(int n,int na,int nb,int m)
{
int ma=3,mb=2,tmp;
if(n==m) return na*ma+nb*mb;
n++;
tmp=na;
na=na+nb;
nb=tmp*2+nb;
return nstep(n,na,nb,m);        
}
把步骤分为两种状态，a 从下边走入 b从左右走入 a可以有3种方法走出，进入1个a状态，2个b状态，b可以有2种方法走出，进入1个a状态，1个b状态 对a  b两种状态分别叠加，最后a*3+b*2就是方法数

[ 本帖最后由 jklqwe111 于 2015-3-31 14:22 编辑 ]

这里是否允许打小广告了，专业承接SMT帖片加工，小批量及样品

#include <stdio.h>

int f(int n) {
    if(n == 1) return 3;
    else if(n == 2) return 7;
    else return f(n - 2) + 2 * f(n - 1);
}

int main(void) {
    int a = 1, b = 2, n = 0, t = 0;

    if((scanf("%d", &n)) == 1 && n > 0) {
        printf("%d\n", f(n));

        while(--n > 0) t = a, a += b, b += 2 * t;

        printf("%d\n", a + b);
    }
    
    return 0;
}