递推公式理解

前置：f(n)为第n步的可能数量。
每一个点可以选向上向右和向左三种选择。再下一次选择时上一次选择的向上可以有三种选择，其余的可以有两种选择。所以，选择上的会多一种选择机会。我们提取公因式，每一个点都有两种选择即2*f(n-1),特殊选择向上的时会多一次，而再上一次时每一个点都有一次选择向上的可能性，所以是f(n-2).
得出：f(n) = f(n-1)*2+f(n-2)