一.題目
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青蛙跳上一個n級的臺階總共有多少種跳法，
二.題目決議
假設我們從最后往前面跳，令最后一次跳的次數為f(n)，那么f(n)=f(n-1)+f(n-2)+....+f(1)，因為每往回跳一次，則可以往回跳1，2，3，4，.....n級，而隨便在x級別臺階處往回跳,都具有f(x)種跳法，假設在第n-3級臺階，那么往回則有f(n-3)種跳法，因此f(n)=f(n-1)+f(n-2)+....+f(1)
我們考慮只往回跳了一級臺階的情況，那么這個時候往回跳的跳法一共有f(n-1)種，展開有f(n-1)=f(n-2)+f(n-3)+.....f(2)+f(1)，正好可以替換掉f(n)的展開式，從f(n-2）開始向后的部分，因此可以得到f(n)=2f(n-1)的運算式，這個運算式則可以用于我們遞回求解，但是由于時間復雜度的緣故，我們使用迭代方法求解，解答的代碼如下：
class Solution: def jumpFloorII(self, number): # write code here if number==1: return 1 else: ret=0 a=1 for i in range(2,number+1): ret=2*a a=ret return ret
得解！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5278.html
標籤：其他
上一篇：正則運算式