問題描述：

一只青蛙要跳上n級(jí)臺(tái)階，它每次可以跳 1級(jí)或者2級(jí)。問：青蛙有多少種不同的跳法可以跳完這些臺(tái)階？

舉個(gè)例子：

假設(shè)臺(tái)階數(shù) n = 3 ，我們來看看青蛙有多少種跳法。?

可能的跳法：
1. 跳1級(jí)，再跳1級(jí)，再跳1級(jí)。（1+1+1）
2. 跳1級(jí)，再跳2級(jí)。（1+2）
3. 跳2級(jí)，再跳1級(jí)。（2+1）

所以，當(dāng) n = 3 時(shí)，總共有 3種跳法。

規(guī)律是什么？

我們可以發(fā)現(xiàn)，青蛙跳到第 \( n \) 級(jí)臺(tái)階的跳法數(shù)，取決于它跳到前兩級(jí)臺(tái)階的跳法數(shù)：
1. 如果青蛙最后一步跳 1級(jí)，那么它之前一定是從第 n-1 級(jí)跳上來的。
2. 如果青蛙最后一步跳 2級(jí)，那么它之前一定是從第 n-2 級(jí)跳上來的。?

遞推公式：?

f(n) = f(n-1) + f(n-2)
其中：
?f(1) = 1 （只有1級(jí)臺(tái)階，只有一種跳法）
?f(2) = 2 （2級(jí)臺(tái)階，可以跳1+1，或者直接跳2）?

具體計(jì)算：

我們用一個(gè)表格來計(jì)算 \( f(n) \) 的值：?

臺(tái)階數(shù)n	跳法數(shù)f(n)	計(jì)算方式
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
...	...	...

代碼實(shí)現(xiàn)：

用代碼來計(jì)算f(n)的值：?

def jump_ways(n):if n <= 0:return 0elif n == 1:return 1elif n == 2:return 2# 初始化前兩級(jí)臺(tái)階的跳法數(shù)prev1, prev2 = 1, 2  # f(1) = 1, f(2) = 2# 從第3級(jí)開始計(jì)算for i in range(3, n + 1):current = prev1 + prev2prev1, prev2 = prev2, currentreturn prev2# 示例
n = 5
print(f"跳上 {n} 級(jí)臺(tái)階的跳法數(shù)：{jump_ways(n)}")

輸出：

跳上 5 級(jí)臺(tái)階的跳法數(shù)：8?

總結(jié)：

?跳到第 n 級(jí)臺(tái)階的跳法數(shù)，等于跳到第 n-1 級(jí)的跳法數(shù)，加上跳到第n-2級(jí)的跳法數(shù)。
- 這個(gè)規(guī)律和斐波那契數(shù)列是一樣的。
- 通過動(dòng)態(tài)規(guī)劃，我們可以高效地計(jì)算出結(jié)果。