跟learnjiawa一起每天一道算法編程題，既可以增強對常用API的熟悉能力，也能增強自己的編程能力和解決問題的能力。算法和數據結構，是基礎中的基礎，更是筆試的重中之重。

• 不積硅步，無以至千里；
• 不積小流，無以成江海。

題目描述

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法(先后次序不同算不同的結果)。

我的想法

1. 題目給定兩種跳法，1階或者2階，將n級臺階的跳法總數記為f(n)
2. 那么假定第一次跳的是一階，那么剩下的是n-1個臺階，跳法是f(n-1);
3. 假定第一次跳的是2階，那么剩下的是n-2個臺階，跳法是f(n-2)
4. 所以n級臺階的總跳法為: f(n) = f(n-1) + f(n-2)
5. 只有一階的時候 f(1) = 1 ,只有兩階的時候可以有 f(2) = 2
6. 可以發現最終得出的是一個首項為1的斐波那契數列：1 2 3 5 8 …..
7. 轉換為了上一題，所以解題辦法完全相同，也存在遞歸或用空間換時間的兩種方法

解題方法1

解題方法2

代碼測試

測試代碼控制臺輸出:

總結

題目主要考察遞歸和循環的相關知識點，先實現，再優化，迅速解題。

參考文獻

[1]程杰. 大話數據結構. 北京：清華大學出版社， 2011.

更多

對我的文章感興趣，點個關注是對我最大的支持，持續更新中……
關注微信公眾號LearnJava，發現更多精彩。