爬楼梯问题

今天看到一个斐波纳切问题的变形，觉得很有意思，遂记录一下：

一个青蛙爬楼梯，他可以一次跳一节台阶，也可以跳两节，还可以后退一节，问：高度为n的台阶共有多少种方式到达。

首先分析一下，对任意一个位置i（i>2)，到达的方式与i+1, i-1, i-2 三个位置有关，即s(i) = s(i+1) + s(i-1) + s(i-2)，而不在位置i上停留到达位置i+1的方式只有一种：从i-1位置跳2节，即s(i+1)=s(i-1), 即s(i) = 2s(i-1) + s(i-2)，有了状态转移方程，我们即可进行求解。

def solve(n):
    if n == 1:
        return 2
    elif n == 2:
        return 3
    return 2*solve(n-1) + solve(n-2)