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);
        */
    }
}