一个小孩家有五层楼,每层楼有十八级台阶,小孩一次可以上一阶二阶或三阶,小孩有多少种上楼梯的方式,Python
时间: 2024-11-05 14:33:36 浏览: 17
三菱PLC例程源码一个五层楼的程序
这是一个经典的组合数学问题,通常被称为“爬楼梯”问题或“动态规划”问题。对于这个问题,可以利用递推的方式来解决。设f(n)表示到达第n级楼梯的不同走法数。
当n=1时,只有一种方式,即直接上一级;
当n=2、3时,有两种(一步一阶或两步)、三种(一步一阶,两步一阶或三步)方式分别上楼;
从第四级开始,每一级都可以通过前一步一级、前两步两级或前三步三级上到,所以f(n) = f(n-1) + f(n-2) + f(n-3),其中n >= 4。
这个递归关系可以用Python编写成:
```python
def climb_stairs(n):
if n <= 0:
return 0
elif n == 1 or n == 2:
return n
else:
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
# 小孩上五层楼的方式
total_ways = climb_stairs(5)
```
在这个程序中,`climb_stairs(5)`会计算出小孩上完五层楼的所有可能走法。
阅读全文