问题
跳房子，规定总共有n个格子，每次可以选择跳1个格子、2个格子或3个格子，但是下一步不能和当前选择的跳跃距离一样，计算总共有多少种跳房子方案。
分析
这就是经典爬楼梯问题的进阶，仅仅换了个说法，但是比经典的爬楼梯问题难了不少，传统的爬楼梯问题一次可以上1或2个台阶没有连续动作选择的限制，核心解法是可以列出一个斐波那契数列，\(f(n) = f(n-1) + f(n-2)\)，递归的2个特殊终止条件是\(f(1)=1,f(2)=2\)。
参考
上面是我参考的做法，它只限制不能连续爬2个台阶而且没有连续跨越3个台阶的选择，它给\(f(n,status)\)函数中额外添加一个参数status，表示从第n个台阶跨status个台阶（因此到达\(f(n,status)\)的前一次跨越不能跨status个台阶）。当status设置为0时是程序代码入口，表示可以从第n-1、n-2或n-3个台阶分别攀爬到第n个台阶。
Python3代码
# 求攀爬方案的总数目：
# 1. 共有n个台阶
# 2. 每次可以向上爬1、2或3个台阶
# 3. 相邻的下一次不能和本次攀爬的台阶数相同
def F(N, status):
if N < 0:
return 0
elif N == 0: # status is 1 2 or 3 没有任何限制 因为这必定是爬台阶的第一步，没有之前步骤长度的限制
return 1
elif N == 1:
if status == 1:
return 0
else: # status is 2 or 3
return 1
elif N >= 2:
if status == 0:
return F(N-1,1) + F(N-2,2) + F(N-3,3)
elif status == 1:
return F(N-2,2) + F(N-3,3)
elif status == 2:
return F(N-1,1) + F(N-3,3)
elif status == 3:
return F(N-1,1) + F(N-2,2)
if __name__ == '__main__':
n = 5
print(f"When n = {n},F numbers: {F(n, 0)}")
执行效果：
验证上述结果
代码以\(n=5\)个台阶为例做测试，爬楼方案和算法伪代码如下图所示
千万要注意递归算法的边界条件：n为负数、0或1的时候。
- 若n为负数，是不合理的，例如\(f(-1,status=3)\)渴望从-1一次爬3个台阶到2，是无解的，因此\(f(n<0,status)=0\)。
- 若n为0，无论\(status\)值为1、2或3，值都为1；这正是爬楼者在起点最初始的选择，选择不受历史的限制（因为这就是最最最开头，没有历史）。
- 若n为1，注意\(f(1,1)\)不合理，值为0，因为0=>1=>2是连续爬1个楼梯的不满足规则；\(f(1,2)=f(1,3)\)都是合理的，值为1，分别代表了0=>1=>3和0=>1=>4的爬楼梯顺序。