这一题光看字面意思还是很难推出递推式的，我们来看一张图：
以上是一张当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];
代码如下：
