admin 管理员组

文章数量: 887055

利用递归和动态规划解 剑指offer 第7,8,9题思路解析 （斐波那契额，跳台阶，变态跳台阶）

时间限制：1秒  空间限制：32768K  热度指数：286711

题目描述（斐波那契数列）

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

n<=39


不知道斐波那契数列的同学可以看这里啦：

举个例子：

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 

可以看出 第一个数是1第二个数也是1，从第三个数开始就是前两个数的和

第四个是前两个数和的和 也就是2+3=5 ... 3+5 = 8;

了解了斐波那契数列，开始做题咯！

这种题有两种解法，一种是利用了递归思想，也就是不断重复前两个数的操作，去表达后面的数字，可能有些抽象，那么再举个栗子~


最直接能看出来的就是  第2位= 1+1 ，

从而可以得出 第4位=2+1，那么第3位也可以化为1+1所以 第4位=(1+1)+1;

所以 第5位=第4位 +第3位 =((1+1)+1)+(1+1) = 5;


就是这个思路，为了我们下面看的方便 我们用f(n) 表示第n位斐波那契数；


先看递归代码 


public int Fibonacci(int n) {if (n<=0){return 0;}if(n == 1 || n ==2){return 1;}return Fibonacci(n-1) + Fibonacci(n-2);}
代码很简洁，但是这种代码有很大的缺陷，就是当数大的时候，时间复杂度太大，而空间复杂度为O(1)；从时空角度来讲，这种解法并不是最优解，因为它不断地进行了重复的运算(化为1之后在做和)，浪费了大量时间。 那我们可不可以把每一次的结果保存，之后在计算呢？，当然可以了，这就是我们的第二种思路，使用动态规划来进行求解，这样保证了时空的权衡。 把特殊值f(1)和f(2)进行保存，然后通过循环，依次把f(n)进行保存，这样在做f(n+1)操作时候，只要把f(n-1)+f(n)就可以了；

同样代码也很简洁，代码如下：

public int Fibonacci2(int n){if(n<2){return 1;}int num1 = 1;int num2 = 1;int tmp = 0;for (int i = 3; i <= n ; i++) {tmp = num1+num2;//记录f(n)num1 = num2; //准备下一次运算,保证每一次都是f(n) = f(n-1)+f(n-2);num2 = tmp;}return tmp;}

以上就是菲波那切数列的两种解法，接下来我们看看跳台阶和变态跳的解法吧，他们跟菲波那切数列大同小异，其实就是斐波那契的变种，

题目描述(跳台阶)

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 跳台阶的规律如下：f(1) = 1 ,  f(2) = 2 一次跳一下 x2  和一次跳两下，所以两种跳法

f(3) = 1x3  , (1x1)+(2x1) , (2x1) + (1x1) ,三种。

细心的小伙伴可以发现了，这就是斐波那契数列，只不过从f(2) = 2了 

后面仍然是f(n) = f(n-1)+f(n-2);

所以思路仍然有两种，一种递归，一种动态规划，这里就不详解了，直接放代码：

递归：

public int JumpFloor(int target) {if(target<=0){return 0;}if(target==1)return 1;if(target==2)return 2;return JumpFloor(target-1)+JumpFloor(target-2);}
动态规划： 
public int HenTaiJumpI(int n){int num1 = 1;int num2 = 2;int tmp = 0;for (int i = 3; i <= n ; i++) {tmp = num1 + num2;num1 = num2;num2 = tmp;}return tmp;}

接下来解析变态跳，变态跳这个问题是跳台阶的变种，

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这里我们仍然以3个台阶为例， f(1) 就只有一种，没毛病。

f(2) 1x2 + 2x1 两种

f(3) (1x3)+(2x1 + 1x1) + (1x1 + 2x1) +(3x1) 四种  

得出结论 f(n) = f(n-1) * 2;

得出了结论，我们继续用两种思路来解这道题和上面的思路雷同，只不过判断条件变成了*2

递归：

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

动态规划:


public int HenTaiJumpII(int n){int num1 = 1;int tmp = 0;for (int i = 3; i <= n ; i++) {tmp = 2*num1;num1 = tmp;}return 2*tmp;}


本文标签： 利用递归和动态规划解剑指offer第7 8 9题思路解析 （斐波那契额，跳台阶，变态跳台阶）

版权声明：本文标题：利用递归和动态规划解剑指offer第7,8,9题思路解析 （斐波那契额，跳台阶，变态跳台阶） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/free/1699182872h335243.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。