CQUPT Python 候先生爬楼梯

【问题描述】

侯先生每天都会爬楼梯锻炼身体，他有时候一次上跨一级，有时候一次上跨两级...有一天侯先生想弄明白一个很难的问题：从最下面的第1级开始到顶端的第n级一共有多少种走法呢？比如n是3时，有两种走法（或者直接从第1级上跨两步到第3级，或者从第1级跨一步到2级再跨一步到第3级）。‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

请你帮帮侯先生，给你n（1<n<40）的值，你帮忙计算并输出有多少种爬到顶端的方法。

【输入形式】

输入n的值，n是1到40之间的整数。

【输出形式】

输出一共有多少种从第1级台阶到第n级台阶的走法。

【样例输入】

4

【样例输出】

3

【完整代码】

def fun(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n == 3:
        return 2
    else:
        return fun(n - 1) + fun(n - 2)

n = int(input())
print(fun(n))

【代码讲解】

状态转移式：fun(n) = fun(n-1) + fun(n-2)

因为一次只能爬一级或二级的楼梯，所以 爬到n级楼梯的方法数 = 爬到n-1级楼梯的方法数 + 爬到n-2级楼梯的方法数。因为是从第一级开始的，fun(1) = 0，fun(2) = 1，fun(3) = 2，后面就可以靠递归。

这题算是经典的动态规划问题，写成列表的情况可能更多见，下面给出代码

n = int(input())
# 初始化dp，n+3是为了即使n=1，也能正确传入dp[3]
dp = [0] * (n + 3)
# 为了直观，空置了dp[0]
dp[1] = 0
dp[2] = 1
dp[3] = 2
# 递归
for i in range(4, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])