剑指Offer | 变态跳台阶

谁践踏了优雅 2022-05-25 12:39 175阅读 0赞

做了个剑指Offer的题目目录，链接如下：  
[https://blog.csdn.net/mengmengdastyle/article/details/80317246][https_blog.csdn.net_mengmengdastyle_article_details_80317246]  
一、题目  
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。  
二、思路  
(1) 举例找规律  
f(1) = 1  
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。  
f(3) = f(3-1) + f(3-2) + f(3-3)  
…  
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)  
（2）简化  
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1)  
= f(0) + f(1) + f(2) + f(3) + … + f(n-2)  
f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1) = f(n-1) + f(n-1)  
可以得出：  
f(n) = 2\*f(n-1)  
（3）得出最终结论,在n阶台阶，一次有1、2、…n阶的跳的方式时，总得跳法为：  
f(n) = 1 ,(n=0 )  
f(n) = 1 ,(n=1 )  
f(n) = 2\*f(n-1),(n>=2)

三、代码

public class Solution {
        public int JumpFloorII(int target) {
            if(target < 1){
                return -1;
            }else if(target == 1){
                return 1;
            }else{
                return 2*JumpFloorII(target-1);
            }
        }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer 变态跳台阶

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

叁歲伎倆/ 2024年04月18日 10:04/ 0 赞/ 69 阅读

相关剑指offer - 变态跳台阶

找规律题 public class Solution { public int JumpFloorII(int n) { in

灰太狼/ 2022年09月25日 01:26/ 0 赞/ 151 阅读

相关剑指Offer-变态跳台阶

变态跳台阶题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：仔

谁借莪１个温暖的怀抱￠/ 2022年08月04日 12:50/ 0 赞/ 181 阅读

相关剑指offer（C++）——变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路：记n级台阶的跳法总数目为f

爱被打了一巴掌/ 2022年06月17日 11:11/ 0 赞/ 50 阅读

相关剑指Offer | 变态跳台阶

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

谁践踏了优雅/ 2022年05月25日 12:39/ 0 赞/ 176 阅读

相关剑指offer：变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。因为n级台阶，第一步有n种跳法：跳1级、跳2级

快来打我*/ 2022年04月14日 05:13/ 0 赞/ 188 阅读

相关剑指Offer-变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。初步解题思想：跳上一级台阶有1中跳法，跳上两级

系统管理员/ 2022年03月01日 05:40/ 0 赞/ 181 阅读

相关剑指offer-变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。实现思想 ①这里的f(n) 代表的是n个

叁歲伎倆/ 2022年02月15日 20:51/ 0 赞/ 232 阅读

相关剑指offer 变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。【分析】因为n级台阶，第一步有n种跳法：跳

男娘i/ 2022年02月01日 07:27/ 0 赞/ 201 阅读

相关剑指offer：变态跳台阶

试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：同理，从后往前想： f(n) =

Love The Way You Lie/ 2021年06月24日 16:00/ 0 赞/ 344 阅读