剑指offer—斐波那契数列 解答

剑指offer—斐波那契数列

题目描述

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。


示例 1:

输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2:

输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3:

输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.

思路

本题有三种方法,依次优化

  • 递归
  • 动态规划:使用数组存储每个位置的值
  • 优化版本动态规划:不使用数组存储每个位置的值,而用两个变量分别存储前一个pre和前前一个prepre的值,在循环中计算前一个与后一个相加再把值重新赋给这两个变量

递归

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }else{
            return Fibonacci(n-1) + Fibonacci(n-2);
        }
    }
}

动态规划

使用数组存储计算过的值,需要的时候再拿出来,典型的动态规划

public class Solution {
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }
        int [] dp = new int[n+1];//用该数组存储计算过的值
        for(int i=0;i<n+1;i++){
            if(i==0){
                dp[i] = 0;
            }else if(i==1){
                dp[i] = 1;
            }else{
                dp[i] = dp[i-2]+dp[i-1];
            }
        }
        return dp[n];
    }
}

更优化的动态规划

不使用数组存储每个位置的值,而用两个变量分别存储前一个pre和前前一个prepre的值,在循环中计算前一个与后一个相加再把值重新赋给这两个变量

public class Solution {
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }else if(n<=2){
            return 1;
        }else{
            int pre = 1;//前一个数值
            int prepre = 1;//前前一个数值
            for(int i=3;i<n+1;i++){
                int temp = pre + prepre;//计算当前数值
                prepre = pre;//给前前一个赋值为前一个
                pre = temp;//给前一个赋值为当前
            }
            return pre;//循环结束返回前一个数值
        }
    }
}

拓展

跳台阶

  • 题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

  • 递归
public class Solution {
    public int JumpFloor(int target) {
        if(target<=1){
            return 1;
        }else{
            return JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}
  • 优化的循环
class Solution {
    public int climbStairs(int n) {
        if(n<=2){
            return n;
        }else{
            int pre = 2;//前一个数值
            int prepre = 1;//前前一个数值
            for(int i=3;i<n+1;i++){
                int temp = pre + prepre;//计算当前数值
                prepre = pre;//给前前一个赋值为前一个
                pre = temp;//给前一个赋值为当前
            }
            return pre;//循环结束返回前一个数值
        }
    }
}

变态跳台阶

题目描述

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

思路
  1. 找规律
  2. 台阶可以看成存在或者不存在两种情况,要跳上第n个台阶则第n个台阶一定存在,前n-1个台阶可以存在或者不存在,所以一共有2的n-1次方中情况
代码
public class Solution {
    public int JumpFloorII(int n) {
        return 1<<(n-1);
    }
}

矩形覆盖

题目描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

思路
代码
public class Solution {
    public int RectCover(int target) {
        if(target<=2){
            return target;
        }else{
            return RectCover(target-1)+RectCover(target-2);
        }
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/fib-array.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!