一.題目：
一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果），
二.題目分析
拿到這個題目我們冥思苦想也沒有想到一個好的想法，于是從最簡單的找規律開始吧！
另臺階的級數為n，跳法的數量為ret.
n=1, ret=1
n=2, ret=2
n=3, ret=3
n=4, ret=5
n=5, ret=8
如下圖所示:
從中分析可得ret等于上一個ret的值加上 上上個ret的大小，就如同斐波那契數列一樣，但是這只是一個猜想，具體是不是這樣的呢？
我們換一個思考的方向，讓青蛙從第n個臺階往回跳，記在第n個臺階時可能跳的跳法為f(n)個，假設它往回跳只跳了一格，那么停留在n-1處，還有f(n-1)種跳法，假設他往回跳了2格，那么它還具有f(n-2)中跳法，一共就具有這兩種情況，因此f(n)=f(n-1)+f(n-2)，這個運算式正好和斐波那契數列的遞回解法的運算式相同，因此也可以使用同樣的迭代解法來求解這個問題，同時這也證明了我們之前的猜想是正確的，如下圖所示：
三.代碼實作
代碼實作就很簡單了，實作和斐波那契數列差不多，如下所示：
# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here if number<1: return 0#在Number小于1的時候 if number==1: return 1 if number==2: return 2 ret=0 a=1 b=2 for i in range(3,number+1): ret=a+b a=b b=ret return ret
得解，牛客網上顯示：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6731.html
標籤：其他