JZ8 跳台阶 java

• 一、题目
• • 1.思路：
  • 2.代码：

一、题目

1.思路：

(1) 方法一：

动态规划：

由题知：

第一个台阶：1种方法

第二个台阶：2种方法

第三个台阶：第二个台阶+第一个台阶方法总和=1+2=3

第四个台阶：第三个台阶+第二个台阶方法总和=3+2=5

第五个台阶：第四个台阶+第三个台阶方法总和=5+3=8

…

第target台阶：第target-1个台阶+第target-2个台阶方法总和

所以只要通过循环，每个台阶跳的方法都是前两个台阶的总和，只要加到target就可以得到了

注意：上述是第一个台阶由1表示，下面的代码是由数组来实现，所以是从0开始的！不要糊涂！

（2）方法二：

递归：每个台阶都是前两个台阶的方法总和

2.代码：

代码如下：

public class Solution {
    public int jumpFloor(int target) {
        //方法一:动态规划
        /*
        如果target==1，直接返回1
        如果target==2，则直接返回2
        由题知：
        第一个台阶：1种方法
        第二个台阶：2种方法
        第三个台阶：第二个台阶+第一个台阶方法总和=1+2=3
        第四个台阶：第三个台阶+第二个台阶方法总和=3+2=5
        第五个台阶：第四个台阶+第三个台阶方法总和=5+3=8
        ..........
        第target台阶：第target-1个台阶+第target-2个台阶方法总和
        */
        if(target==1){
            return 1;
        }
        if(target==2){
            return 2;
        }
        /*用数组的索引表示第几个台阶用值代表每个台阶的跳法总和
        那么ans[0]=1表示第一个台阶的跳法有1种
        ans[1]=2表示第二个台阶的跳法有2种
        ans[2]=ans[1]+ans[0]=1+2=3表示第三个台阶有前两个调节跳法总和为3种
        ........
        则第target台阶的表示则为ans[target-1]=ans[target-2]+ans[target-3]
        所以只要循环累加,每个台阶都是前两个台阶方法总和，直到加到target，即得到第target台阶的方法总和
        */
        int[] ans=new int[target];
        ans[0]=1;
        ans[1]=2;
        for(int i=2;i<target;i++){
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[target-1];
        /*
        方法二:递归:
        每个台阶都是前两个台阶方法总和
        if(target==1){
            return 1;
        }
        if(target==2){
            return 2;
        }
        return JumpFloor(target-1)+JumpFloor(target-2);
        */
    }
}