动态规划问题——青蛙跳台阶案例分析

问题描述：

一只青蛙要跳上n级台阶，它每次可以跳 1级或者2级。问：青蛙有多少种不同的跳法可以跳完这些台阶？

举个例子：

假设台阶数 n = 3 ，我们来看看青蛙有多少种跳法。 

可能的跳法：
1. 跳1级，再跳1级，再跳1级。（1+1+1）
2. 跳1级，再跳2级。（1+2）
3. 跳2级，再跳1级。（2+1）

所以，当 n = 3 时，总共有 3种跳法。

规律是什么？

我们可以发现，青蛙跳到第 \( n \) 级台阶的跳法数，取决于它跳到前两级台阶的跳法数：
1. 如果青蛙最后一步跳 1级，那么它之前一定是从第 n-1 级跳上来的。
2. 如果青蛙最后一步跳 2级，那么它之前一定是从第 n-2 级跳上来的。 

递推公式： 

f(n) = f(n-1) + f(n-2)
其中：
 f(1) = 1 （只有1级台阶，只有一种跳法）
 f(2) = 2 （2级台阶，可以跳1+1，或者直接跳2） 

具体计算：

我们用一个表格来计算 \( f(n) \) 的值： 

台阶数n	跳法数f(n)	计算方式
1	1	只有一种跳法：1
2	2	两种跳法：1+1或2
3	3	f(2）+f(1)=2+1
4	5	f(3)+f(2)=3+2
5	8	f(4)+f(2)=5+3
...	...	...

代码实现：

用代码来计算f(n)的值： 

def jump_ways(n):if n <= 0:return 0elif n == 1:return 1elif n == 2:return 2# 初始化前两级台阶的跳法数prev1, prev2 = 1, 2  # f(1) = 1, f(2) = 2# 从第3级开始计算for i in range(3, n + 1):current = prev1 + prev2prev1, prev2 = prev2, currentreturn prev2# 示例
n = 5
print(f"跳上 {n} 级台阶的跳法数：{jump_ways(n)}")

输出：

跳上 5 级台阶的跳法数：8 

总结：

 跳到第 n 级台阶的跳法数，等于跳到第 n-1 级的跳法数，加上跳到第n-2级的跳法数。
- 这个规律和斐波那契数列是一样的。
- 通过动态规划，我们可以高效地计算出结果。