斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368…

这个数列从第3项开端，每一项都等于前两项之和。

在数学上，斐波那契数列界说如下：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n – 1) + F(n – 2)，其间n > 1

咱们来看一道斐波那契数列的算法题

剑指 Offer 10- I. 斐波那契数列

标题

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的界说如下：

F(0) = 0, F(1) = 1

F(N) = F(N – 1) + F(N – 2), 其间 N > 1.

斐波那契数列由 0 和 1 开端，之后的斐波那契数便是由之前的两数相加而得出。 答案需求取模 1e9+7（1000000007），如核算初始成果为：1000000008，请回来 1。

示例 1：

输入：n = 2

输出：1

示例 2：

输入：n = 5

输出：5

提示：

  • 0 <= n <= 100

来历：力扣（LeetCode）

链接：leetcode-cn.com/problems/fe…

著作权归领扣网络一切。商业转载请联络官方授权，非商业转载请注明出处。

剖析

咱们来剖析一下斐波那契数列：

  1. 数列的第1项和第2项的值都是明确的
  2. 从第3项开端，每一项都等于前两项之和

所以代码十分简略：

class Solution {
    public int fib(int n) {
        // f(0)和f(1)
        if (n <= 1) {
            return n;
        }
        // 递归
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

假定咱们要核算F(4)的值，核算进程如下：

从斐波那契数列到动态规划

  1. 核算F(4)，由于4 > 1，代入公式F(N) = F(N – 1) + F(N – 2)得到：F(4) = F(3) + F(2)，所以想要核算F(4)的值，需求先核算F(2)和F(3)的值
  2. 核算F(2)，同理得到F(2) = F(1) + F(0) = 1 + 0 = 1
  3. 核算F(3)，同理得到F(3) = F(1) + F(2)，这儿的F(2)也需求再核算一次，F(2) = F(1) + F(0) = 1 + 0 = 1，终究核算出F(3) = F(1) + F(2) = 1 + 1 = 2
  4. 终究核算出F(4) = F(3) + F(2) = 2 + 1 = 3

可以看到，在核算F(4)的值时，对于F(2)的核算其实是执行了两次，随着N不断增大，呈现重复核算的地方也会越多！

咱们的优化思路便是减少这部分重复核算，当N确守时，F(N)核算一次过后的成果其实是不变的，咱们把它保存下来即可。又由于N > 1时，F(N) = F(N – 1) + F(N – 2)，所以F(N)的核算，其实只依赖于前两项，只需求保存前两项成果即可

优化后的代码：

class Solution {
    public int fib(int n) {
        // 界说f(0)和f(1)
        int a = 0;
        int b = 1;
        // 界说回来的成果，留意这儿result = n
        int result = n;
        // 迭代处理
        while (n > 1) {
            // 按标题要求取模
            result = (a + b) % 1000000007;
            // 后移
            a = b;
            b = result;
            n--;
        }
        return result;
    }
}

动态规划

以下是百度百科关于动态规划的介绍：

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求处理议方案进程最优化的进程。

动态规划算法一般用于求解具有某种最优性质的问题。在这类问题中，或许会有许多可行解。每一个解都对应于一个值，咱们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分化成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分化得到子问题往往不是互相独立的。若用分治法来解这类问题，则分化得到的子问题数目太多，有些子问题被重复核算了很屡次。如果咱们可以保存已处理的子问题的答案，而在需求时再找出已求得的答案，这样就可以防止很多的重复核算，节省时间。咱们可以用一个表来记载一切已解的子问题的答案。不论该子问题以后是否被用到，只需它被核算过，就将其成果填入表中。这便是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 。

从斐波那契数列到动态规划

先可以不必彻底理解动态规划的这些概念，下面咱们经过一个简略的动态规划类算法题，来看看斐波那契数列和动态规划到底有什么类似的地方

剑指 Offer 10- II. 青蛙跳台阶问题

标题

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

答案需求取模 1e9+7（1000000007），如核算初始成果为：1000000008，请回来 1。

示例 1：

输入：n = 2

输出：2

示例 2：

输入：n = 7

输出：21

示例 3：

输入：n = 0

输出：1

提示：

  • 0 <= n <= 100

留意：本题与主站 70 题相同：leetcode-cn.com/problems/cl…

来历：力扣（LeetCode）

链接：leetcode-cn.com/problems/qi…

著作权归领扣网络一切。商业转载请联络官方授权，非商业转载请注明出处。

剖析

标题重点是：青蛙一次可以跳上1级台阶，也可以跳上2级台阶

这是一道最简略的动态规划算法题

动态规划算法基本思想也是将待求解问题分化成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解

咱们来测验将待求解问题分化成若干个子问题：

  1. n = 0，标题示例3已给出，F(0) = 1

  2. n = 1，只有一种跳法，一次跳上1级台阶，所以F(1) = 1

  3. n = 2，第一次可以跳上1级台阶或跳上2级台阶，当第一次跳上1级台阶，那么还剩余1级台阶，有F(1)种跳法；当第一次跳上2级台阶，那么还剩余0级台阶，有F(0)种跳法。所以F(2) = F(1) + F(0)

    从斐波那契数列到动态规划

  4. n = 3，第一次可以跳上1级台阶或跳上2级台阶，当第一次跳上1级台阶，那么还剩余2级台阶，有F(2)种跳法；当第一次跳上2级台阶，那么还剩余1级台阶，有F(1)种跳法。所以F(3) = F(2) + F(1)

    从斐波那契数列到动态规划

  5. …

  6. n，第一次可以跳上1级台阶或跳上2级台阶，当第一次跳上1级台阶，那么还剩余n – 1级台阶，有F(n – 1)种跳法；当第一次跳上2级台阶，那么还剩余n – 2级台阶，有F(n – 2)种跳法。所以F(n) = F(n – 1) + F(n – 2)

    从斐波那契数列到动态规划

经过剖析，咱们发现这便是上面的斐波那契数列：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n – 1) + F(n – 2)，其间n > 1

所以咱们很容易就能写出代码：

class Solution {
    public int numWays(int n) {
        // 界说f(0)和f(1)
        int a = 1;
        int b = 1;
        // 界说回来的成果，留意这儿result = b
        int result = b;
        // 迭代处理
        while (n > 1) {
            // 按标题要求取模
            result = (a + b) % 1000000007;
            // 后移
            a = b;
            b = result;
            n--;
        }
        return result;
    }
}

咱们再来看一道动态规划的算法题

LeetCode198 – 打家劫舍

标题

你是一个专业的小偷，方案偷盗沿街的房子。每间房内都藏有必定的现金，影响你偷盗的仅有限制要素便是相邻的房子装有彼此连通的防盗体系，如果两间相邻的房子在同一晚上被小偷闯入，体系会自动报警。

给定一个代表每个房子寄存金额的非负整数数组，核算你 不牵动警报设备的情况下 ，一夜之内可以偷盗到的最高金额。

示例 1：

输入：[1,2,3,1]

输出：4

解说：偷盗 1 号房子 (金额 = 1) ，然后偷盗 3 号房子 (金额 = 3)。

偷盗到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]

输出：12

解说：偷盗 1 号房子 (金额 = 2), 偷盗 3 号房子 (金额 = 9)，接着偷盗 5 号房子 (金额 = 1)。

偷盗到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

来历：力扣（LeetCode）

链接：leetcode-cn.com/problems/ho…

著作权归领扣网络一切。商业转载请联络官方授权，非商业转载请注明出处。

剖析

标题要求是：核算出在不牵动警报设备的情况下 ，一夜之内可以偷盗到的最高金额

什么情况下不会牵动警报设备：不偷盗相邻的房子

假定房子编号为n，房子内现金为m[n]，前n个房子偷盗最高金额为F(n)

咱们测验拆分一下问题：

  1. n = 0，没有金额可以偷盗，F(0) = 0

  2. n = 1，由于每个房子寄存的金额为非负整数，所以当时房子的金额便是偷盗最高金额，F(1) = m[1]

  3. n = 2，针对当时房子2，有两种挑选：不偷盗和偷盗。当挑选不偷盗当时房子时，那么偷盗的最高金额便是前1(2 – 1)个房子，可以偷盗到的最高金额为F(1)；当挑选偷盗当时房子时，由于要确保不牵动警报设备，也便是不偷盗相邻的房子，所以还能偷盗前0(2 – 2)个房子，当时房子价值为m[2]，偷盗金额为：F(0) + m[2]，所以偷盗最高金额为F(2) = Math.max(F(1), F(0) + m[2])

    从斐波那契数列到动态规划

  4. n = 3，针对当时房子3，有两种挑选：不偷盗和偷盗。当挑选不偷盗当时房子时，那么偷盗的最高金额便是前2(3 – 1)个房子，可以偷盗到的最高金额为F(2)；当挑选偷盗当时房子时，由于要确保不牵动警报设备，也便是不偷盗相邻的房子，所以还能偷盗前1(3 – 2)个房子，当时房子价值为m[3]，偷盗金额为：F(1) + m[3]，所以偷盗最高金额为F(3) = Math.max(F(2), F(1) + m[3])

    从斐波那契数列到动态规划

  5. …

  6. n，针对当时房子n，有两种挑选：不偷盗和偷盗。当挑选不偷盗当时房子时，那么偷盗的最高金额便是前n – 1个房子，可以偷盗到的最高金额为F(n – 1)；当挑选偷盗当时房子时，由于要确保不牵动警报设备，也便是不偷盗相邻的房子，所以还能偷盗前n – 2个房子，当时房子价值为m[n]，偷盗金额为：F(n – 2) + m[n]，所以偷盗最高金额为F(n) = Math.max(F(n – 1), F(n – 2) + m[n])

    从斐波那契数列到动态规划

经过剖析，咱们得出如下表达式：

  • F(0) = 0
  • F(1) = m[1]
  • F(n) = Math.max(F(n – 1), F(n – 2) + m[n])，其间n > 1

当n > 1时，F(n)也是依赖于F(n – 1)和F(n – 2)，本质上也是和斐波那契数列相似

解题代码：

class Solution {
    public int rob(int[] nums) {
        // 特别判别
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int a = 0;
        int b = 0;
        int result = 0;
        // 迭代处理
        for (int i = 0; i < nums.length; i++) {
            // 获取偷盗最高金额：偷盗当时房子时金额和不偷盗当时房子时金额中最高金额
            int c = Math.max(nums[i] + a, b);
            a = b;
            b = c;
            result = Math.max(result, c);
        }
        return result;
    }
}

总结

动态规划类题型的一种，经过选或不选，选一或选二，测验将待求解问题分化成若干个子问题，终究会得到类似于斐波那契数列的效果，即F(n)会依赖于F(n – 1)和F(n – 2)