題目
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)裆操。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）
分析
臺(tái)階 解法
1 1
2 1,1 2
3 1,1 2,1 1,1,1
4 1,1,1 2,1,1 1 1,1,1,1 1,1,2 2,2
....
由上面可以看出第 N 次的解法數(shù)量是 N-1數(shù)量加上 N-2 數(shù)量
F(n) = F(n-1) + F(n-2)
和斐波那契數(shù)列類似, 可以用遞歸實(shí)現(xiàn)
代碼實(shí)現(xiàn)
/**
* 暴力計(jì)算, 遞歸, 自上向下
*/
@Test
public void test() {
int ret = JumpFloor(10);
System.out.println("test: " + ret);
}
public int JumpFloor(int target) {
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
public int[] mCache = null;
/**
* 通過(guò)緩存優(yōu)化計(jì)算耗時(shí), 空間換時(shí)間, 自上向下
*/
@Test
public void test2() {
int target = 10;
mCache = new int[target + 1];
int ret = JumpFloor2(target);
System.out.println("test2: " + ret);
}
public int JumpFloor2(int target) {
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
// 緩存計(jì)算結(jié)果, 如果未設(shè)值就賦值, 如果有就直接返回, 不需要再重復(fù)計(jì)算
if (mCache[target] == 0) {
mCache[target] = JumpFloor(target - 1) + JumpFloor(target - 2);
}
return mCache[target];
}
/**
* 動(dòng)態(tài)規(guī)劃, 自下向上
*/
@Test
public void test3() {
int target = 10;
int ret = JumpFloor3(target);
System.out.println("tes3: " + ret);
}
public int JumpFloor3(int target) {
int[] cache = new int[target + 1];
cache[0] = 1;
cache[1] = 1;
for (int index = 2; index <= target; index++) {
cache[index] = cache[index - 1] + cache[index - 2];
}
return cache[target];
}
