关键词：
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解法1
本题是【剑指Offer】跳台阶的进化版本。
原来的青蛙只可以跳上1级或2级，即F(n) = F(n - 1) + F(n - 2)
现在的青蛙可以跳上1到n的任意级，按照之前的解题思路，依然先来看F(n)，对于一个n级台阶来说
青蛙第一次可以跳1级，则还剩n - 1级台阶，即F(n - 1)
青蛙第一次可以跳2级，则还剩n - 2级台阶，即F(n - 2)
...
青蛙第一次可以跳n - 1级，则还剩1级台阶，即F(1)
青蛙第一次可以跳n级，即1种跳法
则F(n) = F(n - 1) + F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1
很显然F(1）= 1，在已知F(1)的情况下，我们可以利用递归解这道题，代码如下
实现代码
public int jumpFloorII(int number)
int count = 1;
for (int i = 1; i < number; i++)
count = count + jumpFloorII(number - i);
return count;
解法2
本题的递归算法由于编译器的低效实现不可避免的会存在大量的重复运算，我们可以在递归的基础上做一些优化，详细说明可以查看【剑指Offer】斐波那契数列。或者换一种思路，我们也可以不使用递归。有时候列出结果的前几项，找找规律，可能会有意想不到的收获
对于1级台阶，青蛙只有1 = 2^0^种跳法
对于2级台阶，青蛙有2 = 2^1^种跳法（分别是1,1, 2）
对于3级台阶，青蛙有4 = 2^2^种跳法（分别是1,1,1, 1,2, 2,1, 3）
对于4级台阶，青蛙有8 = 2^3^种跳法（分别是1,1,1,1, 1,1,2, 1,2,1, 2,1,1, 2,2, 1,3, 3,1, 4）
...
不难发现，对于n级台阶，总跳法数是2^n-1^
当然我们也可以通过公式推导出这个结果
由解法1可知
F(n) = F(n - 1) + F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1，则
F(n - 1) = F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1
两个式子合并可得F(n) = 2F(n - 1)，则
F(n - 1) = 2F(n - 2)
F(n - 2) = 2F(n - 3)
即F(n) = 2^2^F(n - 2)，F(n) = 2^3^F(n - 3)
以此类推，F(n）= 2^n-1^F(n - (n - 1)) = 2^n-1^F(1) = 2^n-1^
最终这道题被转换成如何求解2^n-1^，简单的方法是对2连乘n-1次，继续优化的话，可以使用整数的快速幂，【剑指Offer】斐波那契数列也已经有了详细的详解。下面仅放上本题的整数快速幂解法
实现代码
public int jumpFloorII(int number)
number = number - 1;
int count = 1;
int m = 2;
while (number > 0)
if ((number & 1) > 0)
count *= m;
m = m * m;
number = number >> 1;
return count;
解法3
对于求解2^n-1^，可以继续优化，利用左移运算，只使用一行代码就可以得到2^n-1^
对于数字1，左移1位是10，即2 = 2^1^
左移2位是100，即4 = 2^2^
左移3位是1000，即8 = 2^3^
以此类推，左移n位，就是2^n^
要求2^n-1^，只需要将数字1左移n-1位，对应的代码如下
实现代码
public int jumpFloorII(int number)
return 1 << (number - 1);
剑指offer：变态跳台阶(代码片段)
目录题目解题思路具体代码题目题目链接剑指offer：变态跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路这题的名字和题面都和跳台... 查看详情
剑指offer变态跳台阶(代码片段)
...蛙跳上一个n级的台阶总共有多少种跳法。解法1本题是【剑指Offer】跳台阶的进化版本。原来的青蛙只可以跳上1级或2级，即F(n)=F(n-1)+F(n-2)现在的青蛙可以跳上1到n的任意级，按照之前的解题思路，依然先来看F(n)，对于一个n级台... 查看详情
剑指offer-java-变态跳台阶(代码片段)
变态跳台阶题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：packagecom.hlq.test;/***@authorhelongqiang*@date2020/5/1120:34*//***一只青蛙一次... 查看详情
剑指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;... 查看详情
剑指offer变态跳台阶(代码片段)
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路：做一个简单的数学推导，令跳上一个n级台阶总共的跳法为F(n)，F(n)=F(n-1)+F(n-2)+....+F(0)=F(n-1)+F(n-1)... 查看详情
剑指offer[9]——变态跳台阶(代码片段)
题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这个题目是跳台阶的进阶版，其实跟大家分析一下，这道题其实比上一道题简单。在这道题目中，... 查看详情
剑指offer9.变态跳台阶(代码片段)
9.变态跳台阶题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路与上题相似，假设要到3级，那么可以从0，1，2级直接到三级，那么f3=f1+f2+1，f2=f1+1，f3=... 查看详情
剑指offer变态跳台阶
【问题描述】一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。时间限制：1秒 空间限制：32768K 【AC代码】f(n-1)=f((n-1)-1)+f((n-1)-2)+f((n-1)-3)+·&... 查看详情
剑指offer---变态跳台阶
classSolution{public:intjumpFloorII(intnumber){if(number==1){return1;}elseif(number==2){return2;}else{return(2*jumpFloorII(number-1));}}}; 查看详情
[剑指offer]变态跳台阶
题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 a[1]=1a[n]=a[n-1]+a[n-2]+...+a[1]+1a[n-1]=a[n-2]+...+a[1]+1=>a[n]=a[n-1]+a[n-1]=2*a[n-1]=>a[n]=2^(n-1)逻辑明白了... 查看详情
剑指offer-青蛙变态跳台阶-全概率公式
《剑指offer》题目：变态跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题目分析：f(0)=1;表示n级台阶一次跳n级，只有一种跳法f(1)=1;f(2)=2;f(3)=f(2)+f(1)+f(0)...f(n)=f(n-1)+f(n-2)+.... 查看详情
9剑指offer--变态跳台阶
题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解题思路：可知本题f(n)=f(1)+f(2)+...+f(n-1)+1;通过数学归纳法得到f(n)=2^(n-1)1#include<iostream>2using... 查看详情
剑指offer变态跳台阶(代码片段)
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：1//动态规划版2classSolution3public:4intjumpFloorII(intnumber)5if(number==0)6return0;7intcount=1;8for(inti=1;i&... 查看详情
剑指offer变态跳台阶(代码片段)
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：1//动态规划版2classSolution3public:4intjumpFloorII(intnumber)5if(number==0)6return0;7intcount=1;8for(inti=1;i&... 查看详情
[剑指offer]2.变态跳台阶
题目一仅仅青蛙一次能够跳上1级台阶，也能够跳上2级……它也能够跳上n级。求该青蛙跳上一个n级的台阶总共同拥有多少种跳法。思路用Fib(n)表示青蛙跳上n阶台阶的跳法数，设定Fib(0)=1；当n=1时。仅仅有一种跳法，即1阶跳，即F... 查看详情
剑指offer九之变态跳台阶
一、题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。二、思路1、关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:f(1)=1f(2)=f(2-1)+f(2-2) &nbs... 查看详情
剑指offer---09---动态规划：变态跳台阶
https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 题意青蛙的跳法可以有n种就是 查看详情