剑指offer 8.跳台阶

谁践踏了优雅 2022-02-25 04:10 159阅读 0赞

> **时间限制：1秒 空间限制：32768K**  
> **题目描述**  
> 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

**思路:** 典型的斐波那契算法思路,  
1.假设当有n个台阶时假设有f(n)种走法。  
2.青蛙最后一步要么跨1个台阶要么跨2个台阶,只有这两种情况。  
3.当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。  
4. 当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法。  
5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。  
6.找出递推公式后要找公式出口，即当n为1、2时的情况，显然n=1时f(1)等于1，f(2)等于2  
7可得公式为:. f ( n ) = \{ 1 , n=1 2 , n=2 f ( n − 1 ) + f ( n − 2 ) , (n>2,n为整数) f(n)= \\begin\{cases\} 1,& \\text\{n=1\}\\\\ 2,& \\text\{n=2\}\\\\ f(n-1)+f(n-2),& \\text\{(n>2,n为整数)\} \\end\{cases\} f(n)=⎩⎪⎨⎪⎧1,2,f(n−1)\+f(n−2),n=1n=2(n>2,n为整数)  
代码如下:

public class Solution { 
          public int JumpFloor(int target) { 
            if (target <= 0) { 
                return -1;
            } else if (target == 1) { 
                return 1;
            } else if(target == 2) { 
                return 2;
            } else { 
                return JumpFloor(target - 1) + JumpFloor(target - 2);
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】8跳台阶

/ 题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 / public

迈不过友情╰/ 2023年10月17日 18:39/ 0 赞/ 47 阅读

相关剑指Offer-跳台阶

跳台阶题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：其实仔细分析一下，可以发现

叁歲伎倆/ 2022年08月04日 12:50/ 0 赞/ 163 阅读

相关剑指Offer | 跳台阶

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

雨点打透心脏的1/2处/ 2022年05月25日 11:20/ 0 赞/ 191 阅读

相关剑指offer：跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。跳台阶还是个斐波那契数列 c

冷不防/ 2022年04月14日 05:13/ 0 赞/ 221 阅读

相关剑指Offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。初步解题思路：这题与[斐波那契数列][

深碍√TFBOYSˉ_/ 2022年03月01日 01:20/ 0 赞/ 205 阅读

相关剑指offer 8.跳台阶

> 时间限制：1秒空间限制：32768K > 题目描述 > 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不

谁践踏了优雅/ 2022年02月25日 04:10/ 0 赞/ 160 阅读

相关剑指offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。实现思想对于本题，可以从后往前

梦里梦外;/ 2022年02月17日 05:39/ 0 赞/ 189 阅读

相关【剑指offer】跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。题目解析：当只有一节台阶的时候由于每

深碍√TFBOYSˉ_/ 2021年11月09日 14:16/ 0 赞/ 303 阅读

相关剑指offer--（8）跳台阶

剑指offer–（8）跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路描述 1. 第一步可以

迷南。/ 2021年09月23日 03:38/ 0 赞/ 271 阅读

相关剑指offer：跳台阶

试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。代码：跳到第n台阶有两种方式，从第n-1

た入场券/ 2021年06月24日 16:00/ 0 赞/ 392 阅读