【剑指Offer题解：java】跳台阶

悠悠 2023-01-09 15:56 51阅读 0赞

### 文章目录 ###

*   *  题目
     *  分析
     *  题解
     *   *  1）使用递归
         *  2）动态规划
         *  3）循环求解

## 题目 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

## 分析 ##

显然，由于它可以跳1级台阶或者2级台阶，所以**它上一步必定在第n-1,或者第n-2级台阶**，也就是说**它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]  
**所以可以参考**[**斐波拉契数列**][Link 1]**求解**

## 题解 ##

[**斐波拉契数列**][Link 1]**求解**

### 1）使用递归 ###

/** * 使用递归 * @param target * @return */
        public static int jumpFloor(int target) { 
            if(target<=1)return 1;
            return jumpFloor(target-1)+jumpFloor(target-2);
        }

### 2）动态规划 ###

/** * 使用动态规划 * @param target * @return */
        public static int jumpFloor2(int target){ 
            int[]arr = new int[target+1];
            arr[0]= arr[1] = 1;
            for(int i=2;i<=target;i++){ 
                arr[i] = arr[i-1]+arr[i-2];
            }
            return arr[target];
        }

### 3）循环求解 ###

public static int JumpFloor(int target) { 
           if (target == 0 || target == 1) return target;
            int a = 1, b = 1, c = 0;
            for (int i=2; i<=target; ++i) { 
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]: /images/20221119/19acb570fcf9453a925d280cf3a5122f.png
[Link 1]: https://youkaiyang.blog.csdn.net/article/details/112927202