畔俾桑客網(wǎng)（java實現(xiàn)）
問題描述：
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級非凌。求該青蛙跳上一個n級的臺階總共有多少種跳法金抡。
問題分析：
（數(shù)學(xué)歸納總結(jié)瀑焦，數(shù)列。也可以用遞歸）
也可以用逆推的思路去想梗肝，跳n級臺階榛瓮，可以從n-1級跳上來，也可以從n-2級跳上來巫击，從n-3級跳上來禀晓，依次下去，從第1級跳上去坝锰，或直接跳上去粹懒。所以，跳n級臺階的方法數(shù)相當(dāng)于其它所有臺階數(shù)的方法的總和再加上從0級跳上去顷级，表達式為 f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1凫乖。例如：
當(dāng)跳1級臺階時，f(1) = 1;
當(dāng)跳2級臺階時弓颈，f(2) = f(1) + 1 = 2;
當(dāng)跳3級臺階時帽芽，f(3) = f(2) + f(1) + 1 = 4;
當(dāng)跳4級臺階時，f(4) = f(3) + f(2) + f(1) + 1 = 8;
f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1
f(n-1) = f(n-2) +...+ f(2) + f(1) + 1
-->> f(n) - f(n-1) = f(n-1)
-->>f(n) = 2 * f(n-1)
算法實現(xiàn)：
略
參考代碼：
public class Solution {
public int JumpFloorII(int target) {
int sum = (int)Math.pow(2,target-1);
return sum;
}
}
