演算法(9)瘋狂跳臺階
題目描述
一隻青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
這個問題首先看是很難看出來的,那隻好自己寫寫畫畫找找規律。
笨方法:
f(1) = 1
f(2)= 2
f(3)= 4
f(4)= 8
貌似發現什麼了,有時間的同學可以算算f(5),我是數不下去了。
分析法:
f(n)= f(n-1)+f(n-2)+...+f(2)+f(1)
f(n-1)= f(n-2)+f(n-3)+...+f(2)+f(1)
突然想買一本高中數學書看看了,好熟悉的公式啊~~
結果就是f(n) = 2*f(n-1)
哇咔咔,答案這麼簡潔的嗎?
就是 1 2 4 8 16 32 嗎?
好吧在下年少無知請多包涵。
public static int JumpFloorII(int target) { if (target <= 0) { return 0; } return 1<<--target; }