分析：

这题我的思路比较简洁，虽然当时推了挺久，感觉有必要写篇题解纪念一下。 首先，我们可以根据水平和水平方向将最后一步的走法分为两种。不难看出： n步条件下的走法=n步条件下的最后一步向东/西走的走法+n步条件下最后一步向北走的走法。 (觉得很抽象可以先看图解或者先自己画一下图)

我们若可以解出上述两个量，就可以合成答案。 显然：

1. 在竖直方向上，对于n-1步时，每一种走法都可以继续向北走。
2. 在水平方向上，对于n-1步时，最后一步向北走的走法可以往东和西两个方向走，最后一步往东西走的只能往原方向走。

图解(n=2时的情况，方便理解递推式)：

第一步可以到达的三处地点分别是图中标1的三个点。 在竖直方向上考虑，三个点都可以向上走一步到达2，产生的答案是3x1=3。

而在水平方向上考虑，西侧和东侧的1都只能维持原方向走，北侧的1能往东西任意一边走，产生的答案是2+1x2=4。

合成之后我们得到了走2步的走法是7。（图中5个2不代表有五种走法，只能说有5个可以到达的点）

AC代码(C/C++)

#include<stdio.h>
int a[23];               //喜欢质数所以开23
int main()
{
    int n,x=2,y=1;   //代表1步条件下有2步向水平方向走，1步向竖直方向走
    scanf("%d",&n);
    a[1]=3;          //1步条件下的答案
    for(int i=2;i<=n;i++)
    {
        x+=2*y;      //n-1步的走法中最后一步往东西走的走法不变方向走或者最后一步往北的走法往东和西走
       //等价于x=x+2*y（有没有可能这样更容易理解）
        y=a[i-1];    //n-1步的走法中每一种都可以向北走
        a[i]=x+y;   //向东西和北的走法合成为n步下的所有走法
    }
    printf("%d\n",a[n]);
    return 0;
}