经典问题19-上台阶问题

最新推荐文章于 2024-10-14 23:40:45 发布

可雷曼土

最新推荐文章于 2024-10-14 23:40:45 发布

阅读量1.5k

点赞数

文章标签： python 算法

本文链接： https://blog.csdn.net/ggyhang/article/details/120259894

版权

这篇博客探讨了如何解决一个经典问题——有n级台阶，每次只能迈上1级或2级，要求刚好用偶数步上完n级台阶。作者提供了三种解法，包括递归思想的应用，并通过Python实现了解法。当n=5时，存在4种不同的上台阶方案。博客中还提供了视频资源以帮助理解。

摘要由CSDN通过智能技术生成

题目

有 n 级台阶
每步只允许迈上 1 级或 2 级
要求刚好用偶数步上完 n 级台阶
求有多少种走法

比如，当 n = 5时，
只能 4 步（2步无法）
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
所以，一共有 4 种上台阶的方案。

把走两步看成是一个动作的整体。
这样，完成这个动作后，剩余的台阶仍然要求偶数步上完。
剩余的问题与本问题获得相似性 这是使用递归的关键。

def f(n):
  当 n 很小时，返回结果
  对当前的局面，连走两步有哪些走法？
  for 所有走法:
    令，每种走法消耗的台阶数为 x
    所有走法的 f(n-x) 求和 => t
  返回 t

考虑定义两个问题：
f1(n) 上 n 级台阶，要求奇数步完成，方案数？
f2(n) 。。。。。，要求偶数步完成，。。。（即题目中的所求问题）
这样，
f1 中走一步后，可以调用 f2
f2 中走一步后，可以调用 f1
间接递归完成求解

我们假设根本没有偶数步这个要求，
这样就变成了简单的递归问题。
但，
我们可以增加参数，定义辅助函数：
f(n, m)
n 仍然表示剩余的台阶数
m 表示已经走过的步数
这样一来，当递归结束时，可以判断 m 是否符合要求，从而舍弃不合格的方案。

# 上台阶问题
# n 级台阶
# 每次只能上 1 级或 2 级
# 要求用偶数步上完台阶
# 求方案数
# 考虑走两步为一个动作单位，有多少种走法？
def step(n):
    if n