青蛙变态跳台阶

一只青蛙一次可以跳上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;
            
        }
      
    }
     
}