正文 

当前位置： 首页 > 开发 > java教程

跳台阶问题（递归动态规则变态跳台阶）(代码片段)

evenleo evenleo     2022-10-20     814

关键词：

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

 分析：青蛙每次只有一阶或者两阶两种跳法，那么：
  • 假设第一次跳的是一阶，那么剩下的n-1个台阶，跳法是f(n-1)
  • 假设第一次跳的是两阶，那么剩下的n-2个台阶，跳法是f(n-2)
  • 由上面两种假设可得：f(n) = f(n-1) + f(n-2)
  • 由实际情况可知：f(1) = 1，f(2) = 2
  • 最终得出的是一个斐波那契数列：
                 |  1，n = 1
f(n)   =       |  2, n = 2
                 |  f(n-1) + f(n -2), n >2
 
1、递归方法实现：
 
这种方法是最低级的做法，有很多重复计算，效率很低。
int jumpFloor(int n)

    if(n <= 0)
    return 0;
    if(n <= 2)
    return n;
    return jumpFloor(n-1) + jumpFloor(n-2);
2、动态规则实现： 
 
这种方法利用斐波那契数列从下往上算，避免重复计算，提高效率。
int f(int n)

    if(n <= 0)
    return 0;
    int f = 1;
    int g = 1;
    while(n--)
    
    g = g + f;
    f = g - f;
    
    return f;
 
拓展：变态跳台阶问题
 
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级......它也可以跳上n级。此时该青蛙跳上一个n级的台阶总共有多少种跳法？
 
分析：用f(n)表示青蛙跳上n阶台阶的跳法数，设定f(0) = 1;
当n = 1 时，只有一种跳的方式，一阶跳，f(1) = 1
当n = 2 时，有两种跳的方式，一阶跳和两阶跳，f(2) = f(1) + f(0) = 2
当n = 3 时，有三种跳的方式，第一次跳出一阶后，后面还有f(3-1)中跳法； 第一次跳出二阶后，后面还有f(3-2)中跳法；第一次跳出三阶后，后面还有f(3-3)中跳法，f(3) = f(2) + f(1) + f(0) = 4
当n = n 时，第一次跳出一阶后，后面还有f(n-1)中跳法； 第一次跳出二阶后，后面还有f(n-2)中跳法......第一次跳出n阶后，后面还有 f(n-n)中跳法，即：
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-n) = f(0) + f(1) + f(2) + ... + f(n-1)
又因为 f(n-1) = f(0) + f(2) + f(3) + ... + f(n-2)
两式相减得：f(n) = 2 * f(n-1)    ( n >= 2)
                 |  0，n = 0
f(n)   =       |  1, n = 1
                 |  2 * f(n-1) , n >= 2
 
代码实现：
int f(int n)

    if(n <= 0)
    return 0;
    if(n == 1)
    return 1;
    int f = 1;
    for(int i = 2; i <= n; i++)
    
    f = 2 * f;
    
    return f;

 

 

跳台阶，变态跳台阶，矩阵覆盖(代码片段)

一、跳台阶1、问题描述跳台阶:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。2、代码classSolution:defjumpFloor(self,number):#writecodeherea=1b=1foriinrange(number... 查看详情

变态跳台阶（递归算法）

台阶的级数：1,2,3,4,5,6.....对应的跳法：1,2,4,8,16,32....最终结论 在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：|1,(n=0)f(n)=|1,(n=1)|2*f(n-1),(n>=2) packagesuanfati;/**变态跳台阶*一只青蛙一次可以跳上1级台阶，也可以... 查看详情

20191026-跳台阶(代码片段)

斐波那契数列-矩阵算法(O(lgn))-待补充跳台阶-经典问题递归-basic解法，浪费栈空间动态规划-常规解法，转移方程可以有很多变化打表-按照转移方程提前计算注意：台阶数很多的时候，需要手写大数加法变态跳台阶/观察法跳石板/... 查看详情

变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法思路：数学题，找规律即可intjumpFloorII(intn)intn1=1;while(n>1)n1=n1*2;n--;returnn1;  查看详情

变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：用数学归纳法，容易证明f(n)=2**(n-1)pythonsolution:#-*-coding:utf-8-*-classSolution:defjumpFloorII(self,nu... 查看详情

青蛙变态跳台阶解法

问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。　　这个问题可以想到递归来解决，因为以前遇到过类似的爬楼梯问题，也相当于斐波那契数列。　... 查看详情

剑指offer变态跳台阶(代码片段)

...现代码解法3实现代码题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解法1本题是【剑指Offer】跳台阶的进化版本。原来的青蛙只可以跳上1级或2级... 查看详情

剑指offer：变态跳台阶(代码片段)

...录题目解题思路具体代码题目题目链接剑指offer：变态跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路这题的名字和题面都和跳台阶... 查看详情

剑指offer---变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。publicclassSolutionpublicintJumpFloorII(inttarget)if(target<=0)return0;if(target==1)return1;returnJumpFloorII(target-1... 查看详情

剑指offer09变态跳台阶(代码片段)

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。java版本：publicclassSolutionpublicstaticvoidmain(String[]args)longstartTime=System.currentTimeMillis();System.out.println("第4项的结果... 查看详情

剑指offer-java-变态跳台阶(代码片段)

变态跳台阶题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：packagecom.hlq.test;/***@authorhelongqiang*@date2020/5/1120:34*//***一只青蛙一次... 查看详情

剑指offer[9]——变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这个题目是跳台阶的进阶版，其实跟大家分析一下，这道题其实比上一道题简单。在这道题目中，... 查看详情

剑指offer——变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题解：classSolutionpublic:intjumpFloorII(intnumber)vector<int>dp(number+1,0);dp[0]=1;dp[1]=1;dp[2]=2;for(inti=3;i<=number;... 查看详情

变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上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)时间复杂度O(n... 查看详情

c_cpp变态跳台阶的.cpp(代码片段)

查看详情

9.变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题目解答publicclassSolutionpublicintJumpFloorII(inttarget)if(target<=0)return-1;elseif(target==1)return1;elsereturn2*JumpFlo... 查看详情

剑指offer变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路：做一个简单的数学推导，令跳上一个n级台阶总共的跳法为F(n)，F(n)=F(n-1)+F(n-2)+....+F(0)=F(n-1)+F(n-1)... 查看详情

剑指offer9.变态跳台阶(代码片段)

9.变态跳台阶题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路与上题相似，假设要到3级，那么可以从0，1，2级直接到三级，那么f3=f1+f2+1，f2=f1+1，f3=... 查看详情