题解（全网最详）

这一题光看字面意思还是很难推出递推式的，我们来看一张图：

以上是一张当n == 2时的路线图。从中可以看出从出发点延伸出了三条路径‘1’，‘2’，‘3’。垂直的路径‘2’延伸出了三条新的路径——‘6’、‘7’、‘8’。其中有一条垂直的，两条水平的。而从出发点延伸出的另外两条线路——‘1’、‘3’却只各自延伸出了一条垂直的、一条水平的。

所以从中我们不难看出，垂直的路径会延伸出三条新的；水平的路径会延伸出两条新的，这样就可以开始算递推式了。

我们可以用一个数组a来存放当n == ai时的移动方案总数；用b来存放当前水平的路径数量（并处于叶部分），我们就可以很容易推出：

b[i] = b[i - 1] + (a[i - 1] - b[i - 1]) * 2;
然后：
a[i] = a[i - 1] + b[i];

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[35],b[35];
int main(){
    b[1] = 2;
    a[1] = 3;
    int n;
    cin >> n;
    for(int i = 2;i <= n;i ++){
        b[i] = b[i - 1] + (a[i - 1] - b[i - 1]) * 2;
        a[i] = a[i - 1] + b[i];
    }
    cout << a[n];
    return 0;
}