NC68 跳台阶

NC68 跳台阶

跳台阶_牛客题霸_牛客网 (nowcoder.com)

JZ69 跳台阶

跳台阶_牛客题霸_牛客网 (nowcoder.com)

---

// //递归
// public class Solution {
//     public int jumpFloor(int target) {
//         if(target==0){
//             return 1;
//         }
//         if(target==1){
//             return 1;
//         }
//         if(target==2){
//             return 2;
//         }
//         return jumpFloor(target-1)+jumpFloor(target-2);
//     }
// }


// //迭代1
// public class Solution {
//     public int jumpFloor(int target) {
//         if(target==0){
//             return 1;
//         }
//         if(target==1){
//             return 1;
//         }
//         if(target==2){
//             return 2;
//         }
//         int first=1;
//         int second=2;
//         int third=0;
//         while(target>2){
//             third=first+second;
//             first=second;
//             second=third;
//             target--;
//         }
//         return third;
//     }
// }




// //迭代2
// public class Solution {
//     public int jumpFloor(int target) {
//         if(target==0){
//             return 1;
//         }
//         if(target==1){
//             return 1;
//         }
//         if(target==2){
//             return 2;
//         }
//         int first=1;
//         int second=2;
//         int third=0;
//         for(int i=3;i<=target;i++){
//             third=first+second;
//             first=second;
//             second=third;
//         }
//         return third;
//     }
// }


//11
//动规dp
public class Solution {
    public int jumpFloor(int target) {
//         if(target==0){
//             return 1;
//         }
//         if(target==1){
//             return 1;
//         }
//         if(target==2){
//             return 2;
//         }
        int[] dp=new int[target+1];//target+1防止数组越界
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
}