09 图解剑指Offer 变态跳台阶 Java题解

曾经终败给现在 2023-02-20 08:23 55阅读 0赞

### 08 图解剑指Offer 青蛙跳台阶 Java题解 ###

*  09 图解剑指Offer 变态跳台阶 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 09 图解剑指Offer 变态跳台阶 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

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

### 题解: ###

可以想像青蛙还有最后一步就跳到n阶，由于青蛙可以最多跳n阶，所以青蛙跳上n阶台阶的方法等于之前所有阶跳台阶跳法的总和。由此可推导如下公式:  
f(n) = f(n - 1) +f(n-2) …+f(1)  
f(n-1) = f(n-2) …+f(1)  
f(n) = 2f(n-1)  
f(n) = 2的n-1次幂 n>0

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

public class Solution { 
        public int JumpFloorII(int target) { 
            if(target == 0) return target;
            
            return (int)Math.pow(2, target - 1);
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1) 。  
最坏时间复杂度: O(n)

[Link 1]: https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200625185528809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70