題目描述
一只青蛙一次可以跳上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);
}
