斐波那契数列

斐波那契数列（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项和第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)的值，计算过程如下：流程图-2.jpg

计算F(4)，因为4 > 1，代入公式F(N) = F(N - 1) + F(N - 2)得到：F(4) = F(3) + F(2)，所以想要计算F(4)的值，需要先计算F(2)和F(3)的值
计算F(2)，同理得到F(2) = F(1) + F(0) = 1 + 0 = 1
计算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
最终计算出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级台阶

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

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

我们来尝试将待求解问题分解成若干个子问题：

n = 0，题目示例3已给出，F(0) = 1
n = 1，只有一种跳法，一次跳上1级台阶，所以F(1) = 1
n = 2，第一次可以跳上1级台阶或跳上2级台阶，当第一次跳上1级台阶，那么还剩下1级台阶，有F(1)种跳法；当第一次跳上2级台阶，那么还剩下0级台阶，有F(0)种跳法。所以F(2) = F(1) + F(0)
n = 3，第一次可以跳上1级台阶或跳上2级台阶，当第一次跳上1级台阶，那么还剩下2级台阶，有F(2)种跳法；当第一次跳上2级台阶，那么还剩下1级台阶，有F(1)种跳法。所以F(3) = F(2) + F(1)
...
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)

我们尝试拆分一下问题：

n = 0，没有金额可以偷窃，F(0) = 0
n = 1，因为每个房屋存放的金额为非负整数，所以当前房屋的金额就是偷窃最高金额，F(1) = m[1]
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])
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])
...
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)