青蛙变态跳台阶问题

Dear 丶 2022-05-15 12:50 150阅读 0赞

## 题目描述 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级

跳1级，剩下n-1级，则剩下跳法是f(n-1)  
跳2级，剩下n-2级，则剩下跳法是f(n-2)

所以f(n) = f(n-1) + f(n-2) + ... + f(1)  
因为f(n-1) = f(n-2) + f(n-3 )+ ... + f(1)

所以f(n) = 2 \* f(n-1)。

根据f(1) = 1，f(n) = 2 \* f(n-1)，可以得出f(n) = 2^(n-1)。

或者可以这么分析：每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)种情况。

**第一种方法**使用递归求解的代码如下：

public class Solution {
    
        public static void main(String[] args) {
            Long begintime = System.nanoTime();
            int result = JumpFloorII(10);
            Long endtime = System.nanoTime();
            System.out.println("result="+result+"；用时："+(endtime-begintime)+"ns");
        }
    
        public static int JumpFloorII(int target) {
            if (target < 1) {
                return 0;
            } else if (target == 1) {
                return 1;
            } else {
                return 2 * JumpFloorII(target - 1);
            }
        }
    
    }

程序运算结果：

![70][]

该算法的时间复杂度是O(n)，和求阶乘的时间复杂度类似。这种方法属于**自顶向下**的算法。

也可以使用**自底向上的方法**解决这个问题。代码如下：

第二种方法使用循环求解的代码如下：

public class Solution {
    
        public static void main(String[] args) {
            Long begintime = System.nanoTime();
            int result = JumpFloorII(10);
            Long endtime = System.nanoTime();
            System.out.println("result="+result+"；用时："+(endtime-begintime)+"ns");
        }
    
        public static int JumpFloorII(int target) {
            if(target < 1){
                return 0;
            }
            if(target == 1){
                return 1;
            }
            int a = 1;
            int temp = 1;
            for(int i = 2; i <= target; i++){
                temp = 2 * a;
                a = temp;
            }
            return temp;
        }
    
    }

程序执行结果：

![70 1][]

这种算法的时间复杂度是**O(n)**。

也可以使用**动态规划**解决这个问题，这时的\[**状态转移方程**\]就变成了F(n) = 2\*F(n-1)。

第三种方法使用动态规划求解的代码如下：

public class Solution {
    
        public static void main(String[] args) {
            Long begintime = System.nanoTime();
            int result = JumpFloorII(10);
            Long endtime = System.nanoTime();
            System.out.println("result="+result+"；用时："+(endtime-begintime)+"ns");
        }
    
        public static int JumpFloorII(int target) {
            //第n次走的台阶个数是第n-1次走的台阶个数的2倍
            //所以状态转移方程为 dp[i] = 2*dp[i-1];
            int[] dp = new int[target+1];
            dp[0] = dp[1] = 1;
            for (int i=2; i<=target; ++i) {
                dp[i] = 2*dp[i-1];
            }
            return dp[target];
        }
    
    }

程序执行结果：

![70 2][]

使用动态规划循环执行了n-1次，所以这里动态规划算法的时间复杂度是**O(n)**。

或者可以直接从公式入手，根据推导出的公式f(n) = 2^(n-1)，那么JumpFloorII方法就可以变成如下。

第四种方法使用公式求解的代码如下：

public int JumpFloorII(int target) {
            if (target < 1) {
                return 0;
            }else {
                return (int) Math.pow(2, target-1);
            }
    }

为了更加提高效率，可以把乘法变为左移运算，因为在计算机中移位运算的操作效率要优于乘除法。移位运算可以把算法的时间复杂度降到常数级别，效率还是很高的。但是要注意对于移位运算，答案不要溢出，虽然不用处理但是在面试时要考虑溢出的问题并说明。

第五种方法使用移位运算求解的代码如下：

public int JumpFloorII(int target) {
        if (target < 1) {
                return 0;
            }else {
            return  1<<--target;
            }
    }

或者这样：

public static int JumpFloorII(int target) {
            if(target < 1) return 0;
            if(target == 1) return 1;
            return 2<<(target-2);
    }

这个也要考虑内存溢出的问题。上面两个就是移位运算的解法，移位运算解法的时间复杂度是**O(1)。**

参考:（1）[https://blog.csdn.net/qq\_27703417/article/details/70983672][https_blog.csdn.net_qq_27703417_article_details_70983672]

[70]: /images/20220515/7a3efb384ed4463e9697a7794f516a07.png
[70 1]: /images/20220515/eb89b0223f9f4679821f48dedf57783c.png
[70 2]: /images/20220515/0bab9f1b197047d182961e332cd55bcf.png
[https_blog.csdn.net_qq_27703417_article_details_70983672]: https://blog.csdn.net/qq_27703417/article/details/70983672