回溯、动态规划，用Python解决台阶问题
问题描述：假设总共有6级台阶。每次只能走1级或2级台阶。请问总共有几种走法？每一种走的步骤如何？
类似的问题，我们一般称为【台阶问题】。
我们可以先假设总共只有1级台阶，此时有1种走法，即(1)。
假设总共有2级台阶，此时有2种走法，分别是(1,1)和(2)。
假设总共有3级台阶，此时有3种走法，分别是(1,1,1)、(2,1)和(1,2)。
假设总共有4级台阶，此时有5种走法，分别是(1,1,1,1)、(1,2,1)、(2,2)、(2,1,1)、(1,1,2)。
......
由此，可假设N-1级台阶有M种走法，N-2级台阶有N种走法，则N级台阶应该由M+N种走法。
因此，类似斐波那契数列，可构造函数f(n) = f(n-1) + f(n-2)进行递归求解即可。
但是由图可以看到：递归不可避免重复计算问题。并未达到最优的算法求解效果，可通过自顶向下备忘录法或自底向下计算法解决重复计算问题。
未来可出一篇文章运用上述两种方法改进算法，但本篇文章重点不在于此。所以闲话少叙，直接进入正题：
本文试图运用回溯、动态规划思想，减少重复计算，更好地解决台阶问题。
直接看代码吧，一图胜千言。
# coding='utf-8'
# 定义三个全局变量
# 定义一共有几级台阶
levels = 6
# 定义存储一个解的数组
footstep_list = []
# 定义一个数组容器，用来存储所有的解
footstep_set = []
# 冲突检测函数
def conflict(n) :
global levels, footstep_list, footstep_set
# 如果目前走过台阶数超过定义的台阶数，视为冲突，返回True
if (sum(footstep_list) > levels):
return True
# 如果未超过定义的台阶数，则不冲突，返回False
return False
# 爬楼函数
def find_way(n) :
global levels, footstep_list, footstep_set
# 如果目前list元素之和等于定义的台阶数，打印输出并添加到容器中
if (sum(footstep_list) == levels):
print(footstep_list)
footstep_set.append(footstep_list)
else :
# 因为只能走1，2级台阶，所以i在[1,2]中循环即可
for i in [1, 2]:
footstep_list.append(i)
# 进行冲突检测，如果不冲突，向上爬楼梯
if not conflict(n):
find_way(n + 1)
# 回溯
footstep_list.pop()
if __name__ == "__main__":
find_way(1)
print(len(footstep_set))
要想彻底明白这段代码，最重要是想清楚：什么时候需要回溯？什么时候结束？
个人在初次接触这个问题也思考了许久，最终有了我个人的思考：
①、冲突检测返回True，即存在冲突，说明解不合适，需要回溯；
②、找到一个解并打印输出，递回后进行回溯，寻找走当前步时另外的解；
③、函数递回到n = 1时，函数得到了所有解的集合，代码结束。
好了，本文分享就到这里了。还是不理解的小伙伴可以动手写写看。多思考，总有一天会理解的。
期待下篇文章见。