变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
解法一
跳台阶的延伸。青蛙的第一跳有n种情况，可以跳1级、2级……n级，得出$f(n) = f(n - 1) + f(n - 2) + \cdots + f(0)$。注意这里$f(0)$应该等于1，对应的是青蛙第一跳跳n级的情况。n从小到大循环计算结果并把结果存储起来以便后面计算使用。
解法二
数学推导
\[\begin{aligned} &f(n) = f(n - 1) + f(n - 2) + \cdots + f(0)\\[2ex] &f(n + 1) = f(n) + f(n - 1) + f(n - 2) + \cdots + f(0)\\[2ex] &f(n + 1) = 2f(n) 得出此为等比数列\ 首项f(1) = 1 公比为2\\[2ex] &f(n) = f(1) \cdot 2^{n - 1}\\[2ex] &f(n) = 2^{n - 1} \end{aligned}\]代码
解法一
public class Solution {
public int JumpFloorII(int target) {
if(target <= 0) {
return 0;
} else if(target == 1) {
return 1;
} else {
int[] resultArray = new int[target + 1];
resultArray[0] = 1;
resultArray[1] = 1;
for(int i = 2; i <= target; i++) {
int sum = 0;
for(int j = 0; j < i; j++) {
sum += resultArray[j];
}
resultArray[i] = sum;
}
return resultArray[target];
}
}
}
解法二
public class Solution {
public int JumpFloorII(int target) {
if(target <= 0) {
return 0;
} else if(target == 1) {
return 1;
} else {
return (int)Math.pow(2, target - 1);
}
}
}
PREVIOUS剑指Offer 面试题09-2：跳台阶