題目描述
一只青蛙一次可以跳上1級臺階藤乙,也可以跳上2級……它也可以跳上n級惭墓。求該青蛙跳上一個n級的臺階總共有多少種跳法。
- 解答:也可以用逆推的思路去想腊凶,跳n級臺階拴念,可以從n-1級跳上來褐缠,也可以從n-2級跳上來,從n-3級跳上來队魏,依次下去,從第1級跳上去官帘,或直接跳上去昧谊,所以,跳n級臺階的方法數(shù)相當(dāng)于其它所有臺階數(shù)的方法的總和再加上從0級跳上去呢诬,表達(dá)式為 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)
/**
* 方法1:遞歸综膀。使用遞歸需要知道
* (1)遞歸結(jié)束條件,何時結(jié)束
* (2)以及遞歸的計算方式
*
* @param target
* @return
*/
public int JumpFloorII(int target) {
return loopJump(target);
}
public int loopJump(int target) {
// 遞歸結(jié)束條件
if (target <= 0) {
return 0;
}
// 遞歸初始條件
if (target == 1) {
return 1;
}
return 2*loopJump(target - 1);
}