青蛙变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
方法一：
公式推导
f(n) = f(n-1)+f(n-2)+f(n-3)+f(4)+....+f(0)
f(n-1) = f(n-2)+f(n-3)+f(4)+....+f(0)
代入 f(n) = 2*(f(n-2)+f(n-3)+f(4)+....+f(0)) = 2 * f(n-1)
public class Solution {
public int JumpFloorII(int n) {
//将前面的总数加上去
int sum = 2;
if(n <= 2){
return n;
}
else {
for(int i = 3; i<=n;i++){
sum*=2;
}
}
return sum;
}
}
方法二：
递归
第一种跳 n 步，剩下0步
第二种跳 n-1 步，剩下1步需要跳的情况
第二种跳 n-2 步，剩下2步需要跳的情况
第二种跳 n-3 步，剩下3步需要跳的情况
第二种跳 n-4 步，剩下4步需要跳的情况
每个父问题都可以分解为子问题，递归
可以使用递归
f(n) = f(n-1)+f(n-2)+f(n-3)+f(4)+....+f(0)
public class Solution {
public int JumpFloorII(int n) {
//递归
//自底向上
if(n <= 2 ){
return n;
}
else{
int sum = 1;
while(n>0){
n--;
sum += JumpFloorII(n);
}
return sum;
}
}
}
