题目
题目描述
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。 编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
样例 #1
样例输入 #1
4
样例输出 #1
5
提示
对于 60% 的数据，N≤50； 对于 100% 的数据，1≤N≤5000。
问题分析
我们可以用递归角度解决：
- 当青蛙跳到第 n 级楼梯，可以选择：
- 从第 n-1 级跳到第 n 级（跳 1 级）。
- 从第 n-2 级跳到第 n 级（跳 2 级）。
- 递归关系：
- f(n)=f(n−1)+f(n−2)
- 其中，f(n) 代表跳到第 n 级楼梯的方法总数。
- 并且：
- 如果 n=0，即青蛙在第 0 级楼梯，则 f(0)=0（即什么都不做）。
- 如果 n=1，即青蛙跳到第 1 级楼梯，那么只能跳 1 级，则 f(1)=1。
- f(n)=f(n−1)+f(n−2)
- 问题的递归式：
- 基于以上推理，我们可以列出以下递归关系式：
解题
伪代码：
F(n):
如果 n == 0:
返回1 // 起始点，不需要跳跃，只有一种方式
如果 n == 1:
返回 1 // 只有一种方式跳到第1阶
// 从n-1阶跳到n阶，或从n-2阶到n阶
返回 CountWays(n - 1) + CountWays(n - 2)
Python 实现： 初版：
def F(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return F(n - 1) + F(n - 2)
n = input()
print(F(n))
犯了个低级错误，输入的 n 是字符串。
改正：
def F(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return F(n - 1) + F(n - 2)
n = int(input())
print(F(n))
OK，提交代码：
WA、TLE、RE。。。。。。
应该是效率太低了，难道要用DP解？
DP（动态规划）
- 定义：
- 设 dp[i] 表示青蛙跳到第 n 级台阶的方法数。
- 当 i>=2 时，青蛙可以选择：
- 从第 i-1 级楼梯跳到第 n 级。
- 从第 i-2 级楼梯跳到第 n 级。
- 所以，我们可以列出：
- dp[i]=dp[i−1]+dp[i−2]
- 并且：
- 如果 i=0，dp[0]=1，表示跳到第0阶的方式只有1种（就是不跳）。
- 如果 i=1，dp[1]=1，表示跳到第1阶的方式只有1种（就是跳 1 级）。
- 并且：
- dp[i]=dp[i−1]+dp[i−2]
- 递推关系：
- 那么，我们很容易得出递推公式：
- dp[i]=dp[i−1]+dp[i−2]
- 通过递推公式，从 dp[2] 一直到 dp[n]，逐步计算出结果。
- 那么，我们很容易得出递推公式：
解题（DP）
Python实现：
def F(n):
# 如果 n 为 0 或 1，直接返回 1
if n == 0 or n == 1:
return 1
# 创建一个 dp 数组，存储每阶的跳法
dp = [0] * (n + 1)
# 初始条件
dp[0] = 1 # 第 0 阶只有 1 种方法（不跳）
dp[1] = 1 # 第 1 阶只有 1 种方法（跳 1 步）
# 递推关系，计算从第 2 阶到第 n 阶的方法数
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 返回跳到第 n 阶的方法数
return dp[n]
# 读取输入
n = int(input())
print(F(n))
提交！ AC！ 完美通过！ 本篇题解到此结束，