题解——pythonTip44超级楼梯

本文最后更新于：2025年10月14日 晚上

题目描述：

‘’有一楼梯共n级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第n级，共有多少种走法？
现在给你一个正整数n（0<n<40),请你输出不同的走法数。”

示例

输入：n = 2

输出：1

思路

这题好熟悉，高中数学，就是排列组合了。用m个1步和k个2步走上台阶，可能的走法。

以需要走7步数为例吧：
step 1 零个1：A^7^7

7=1+1+1+1+1+1+1

step 2 一个2：A^1^6

7=2+1+1+1+1+1

…

step 3 两个2：A^2^5/ A^2^2 (重复元素排序问题)

7=2+2+1+1+1

…

step4 三个2：A^3^4/A^3^3

7=2+2+2+1

…

注意事项

  1. 题中的n是台阶的阶数，应与要走的阶梯数区分。如n=1时，应输出0，因为不需要走。
  2. 重复元素排序需考虑重复情况

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def perm(m,k):
    '''排列数函数'''
    fact = 1
    for j in range(m-k+1,m+1):
        fact *=j
    return  fact

steep = n-1 #步数
total=1
if n==1:     #不用走的情况
    print(0)
else:
    for i in range((steep//2)+1):
        if i == 0:
            total = 1
        else:
            total = total +(perm(steep-i,i) / perm(i,i)) #解决重复元素排序重复
    print(int(total))