跳台阶

import java.util.*;

public class Solution {
    public int jumpFloor (int number) {
        if (number == 1) return 1;
        else if (number == 2) return 2;
        else {
            return jumpFloor(number - 1) + jumpFloor(number - 2);
        }   
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    int[] dp = new int[40];
    public int jumpFloor(int num) {
        if (dp[num] != 0) {
            return dp[num];
        }
        if (num == 1 || num == 2) {
            dp[num] = num;
            return dp[num];
        } else {
            int count = jumpFloor(num - 1) + jumpFloor(num - 2);
            dp[num] = count;
            return dp[num];
        }
    }
}

 public int jumpFloor (int number) {
        // write code here
        if(number<2)
        return 1;
        //当n=2时，return得到1+1=2
        else
            return jumpFloor(number-2)+(jumpFloor(number-1));
    }

public int jumpFloor (int number) {
        int[] dp=new int[number+1];//如果不初始化dp[0]，那就存数组的时候从1开始
        if(number==1){  //如果数组下标从1开始，那么这里1的情况就要单独加进去
            return 1;
        }
        dp[1]=1;//到第一个台阶
        dp[2]=2;//到第二个台阶
        for(int i=3;i<number+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloor (int number) {
        return jumpFloor_(0, 1, number);
    }

    private int jumpFloor_(int acc1, int acc2, int number) {
        return number == 0
                ? acc2
                : jumpFloor_(acc2, acc1 + acc2, number - 1);
    }
}

public class Solution {
    public int jumpFloor(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }
        // 跳到i级台阶有多少种跳法
        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            // 第i级可以从前两级跳过来，也可以从前一级跳过来
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

public class Solution {
    public int jumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

public class Prac01 { public static void main(String [] args){ // 一只青蛙一次可以跳上1级台阶，也可以跳上2级。  // 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 // 输入： //        2 // // 返回值： //        2 // // 说明： // 青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2  Scanner scanner = new Scanner(System.in);  int n1 = scanner.nextInt();  if(n1==1){
            System.out.println("1");  }if(n1==2){
            System.out.println("2");  }if(n1==3){ // 111 21 12  n1为3 3位到2位  System.out.println("3");  }if(n1==4){// 1111 211 121 112 22 由4位到3位到2位  System.out.println("5");  }
        
    }
}

public class Solution {
    public int jumpFloor(int target) {
       return jump(target);
    }

    private int jump(int target) {
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        return jump(target - 1) + jump(target-2);
    }
}

public class Solution {
    public int jumpFloor(int target) {
        // 辅助数组：用于存储计算结果，避免重复运算
        int []data = new int[target];

        return jumpFloor(target, data);
    }


    public int jumpFloor(int target,  int[] data) {
        // 递归结束条件1：两阶台阶：2种跳法，一阶台阶：1种跳法
        if (target <= 2) {
            return target;
        }
        // 递归结束条件2：在数组中查找计算过的结果，如果有，则不用计算，节省时间
        if (data[target - 1] != 0) {
            return data[target - 1];
        }
        // 将结果进行保存，避免重复计算
        data[target - 1]  = jumpFloor(target - 1, data) + jumpFloor(target - 2, data);

        return data[target - 1];
    }
}

public class Solution {

    /** 一、自顶向下
    public int jumpFloor(int target) {
       if(target < 0){
            return 0;
        }else if(target== 1){
            return 1;
        }else if(target == 2){
            return 2;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    } */

    /** 二、自底向上  */
   public int jumpFloor(int target) {
       return jumpFloor(0, target);
    }
    /**
     * 递归求解
     * @param n 当前跳了几层台阶
     * @param target 总共有多少层
     * @return 返回有多少种跳法
     */
    public int jumpFloor(int n, int target) {
        if(n > target) return 0; // 如果当前跳的台阶 大于 实际有的台阶，返回跳法0种

        if(target - n == 1) return 1; // 如果当前跳的台阶 与 实际有的台阶，相差1 返回跳法1种
        else if(target - n == 2) return 2; // 如果当前跳的台阶 与 实际有的台阶，相差2 返回跳法2种

        int i = jumpFloor(n + 1, target);   // 当前这一位置跳一层
       int i2 = jumpFloor(n + 2, target); // 当前这一位置跳两层
        return i + i2; // 两种跳法相加
       //return jumpFloor(n + 1, target) + jumpFloor(n + 2, target);      
     }
}

public class Solution {
    public int count=0;
    public int jumpFloor(int target) {
        if(target==0){
            return 0;
        }
        backWard(target,0);
        return count;
    }
    //回溯算法
    public void backWard(int n,int step){
        //如果step刚好累加到等于n，则count++
        if(step==n){
            count++;
            return;
        }
        //优先向上走一步
        if(step+1<=n){
            backWard(n,step+1);
        }
        //其次一步的走完后，再尝试走两不
        if(step+2<=n){
            backWard(n,step+2);
        }
    }

}

//递归
public class Solution {


    int result = 0;

    public int jumpFloor(int target) {
        jum(target);
        return result;
    }

    public void jum(int left){
        if(left>2){
            jum(left-2);
            jum(left-1);
        }else if(left==2){
            jum(left-1);
            result++;
        }else if(left==1){
            result ++;
        }
    }

}