网站的加盟代理,网站建设公司市场,官方网站下载6966,开个网店需要多少资金费用在线题目链接#xff1a;跳台阶 文章目录1、题目描述2、题目分析3、代码3.1 递归方法3.11 Java代码3.12 C代码3.2 动态规划3.21 Java代码3.22 C代码3.3 循环方法3.31 Java代码3.32 C代码4、总结1、题目描述
一只青蛙一次可以跳上1级台阶#xff0c;也可以跳上2级。求该青蛙跳…在线题目链接跳台阶 文章目录1、题目描述2、题目分析3、代码3.1 递归方法3.11 Java代码3.12 C代码3.2 动态规划3.21 Java代码3.22 C代码3.3 循环方法3.31 Java代码3.32 C代码4、总结 1、题目描述
一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法先后次序不同算不同的结果。
2、题目分析
首先我们定义fn为跳到n级台阶时需要的跳法。那么我们可以这样想想要跳到n级台阶只能从n-1级台阶跳上来或者从n-2级台阶跳上来。所以f(n)f(n-1)f(n-2),很明显。这又是斐波那契数列的公式。
只不过在这里f(1)1,f(2)2。如下图 既然我们已经可以得出公式了那就很好写代码。最容易明白的就是递归了上面的公式其实就是一个递归的公式。
下面提供多种解法递归动态规划循环。
3、代码
3.1 递归方法
递归解法很简单
3.11 Java代码
public class Solution {public int JumpFloor(int n) {//递归解法if(n2)return n;return JumpFloor(n-1)JumpFloor(n-2);}
}3.12 C代码
class Solution {
public:int jumpFloor(int n) {//递归解法,超时if(n2)return n;return jumpFloor(n-1)jumpFloor(n-2);}
};我们都知道这种递归解法会有很多重复的计算就像下面的假设我们要计算f(10):
计算f(10)要重复计算两次f8三次f7三次f6这种重复计算对于数据比价大的时候开销是非常大的。所以我们经常说递归虽然好写但是不建议在实现算法的时候使用递归算法。
3.2 动态规划
凡是能用递归写出的代码一定能够用动态规划写出来。
我们知道递归是为了求某一个值而必须先知道另外的几个值后才能求出来。而想要求那另外的几个值还需要再求另外的另外的值就像上面的递归二叉树想要先求f10必须知道f9和发8。想要知道f9又得知道f8和f7…
上面递归是想要计算总体值需要求局部的值想要求局部的值又要求局部的局部的值。
动态规划不是这样动态规划是先从递归的终止条件开始计算也就是说动态规划先计算局部的值然后根据局部的值的累积最终得到整体要求的值。也就是与递归反过来了。
比如针对上面的求f10我们先求f1f2f3…最终肯定会求得f10。这样我们就没有进行重复的计算。每一项都是只计算一次。
看代码就能明白上面说的是什么意思了。下面的ret数组ret[i]代表斐波那契数组的第i项。我们要求得第n项最后求到ret[n]直接返回即可。
3.21 Java代码
public class Solution {public int JumpFloor(int n) {//动态规划if(n1)return n;int[] retnew int[n1];ret[0]0;ret[1]1;ret[2]2;int i;for(i3;in;i){ret[i]ret[i-1]ret[i-2];}return ret[n];}
}3.22 C代码
class Solution {
public:int jumpFloor(int n) {//动态规划//if(n2)return n;int ret[n1];ret[0]0;ret[1]1;ret[2]2;int i;for(i3;in;i){ret[i]ret[i-1]ret[i-2];}return ret[n];}
};3.3 循环方法
所有的递归都可以写成动态规划同理所有的动态规划也一定能写成循环。只不过有的动态规划不好写成循环而已。本题是非常好写成循环的。
循环比动态规划好的原因在于循环只用几个变量循环使用它们得到最终结果不保存之前的计算结果动态规划却需要开辟一个数组将所有计算过的结果保存这很浪费空间。
3.31 Java代码
public class Solution {public int JumpFloor(int n) {//循环if(n2)return n;int ret0;int r01,r12;int i;for(i3;in;i){retr0r1;r0r1;r1ret;}return ret;}
}当然上面使用三个变量我们还可以再减少一个变量使用两个变量
public class Solution {public int JumpFloor(int n) {if(n2)return n;int r11,r22,i;for(i3;in;i){r2r1;r1r2-r1;}return r2;}
}
3.32 C代码
三个变量
class Solution {
public:int jumpFloor(int n) {//循环if(n2)return n;int ret0;int r01,r12;int i;for(i3;in;i){retr0r1;r0r1;r1ret;}return ret;}
};两个变量
class Solution {
public:int jumpFloor(int n) {if(n2)return n;int r11,r22,i;for(i3;in;i){r2r1;r1r2-r1;}return r2;}
};4、总结
注意学会递归动态规划循环三者时间的关系
探讨学习加 个人qq1126137994 个人微信liu1126137994
