第九章动态规划——理论基础，斐波那契数

目录

理论基础

        动态规划（Dynamic Programming）是一种用来解决最优化问题的策略，通过将原问题分解为相互重叠的子问题，把问题分解得足够小。

一、动态规划的常见问题

1. 背包问题：如0/1背包问题，完全背包问题等。
2. 最长公共子序列（LCS）
3. 最短路径问题
4. 打家劫舍
5. 股票问题

二、动态规划的误区

        常见误区是认为所有有重叠子问题的问题都可以用DP解决，实际上，只有具有最优子结构的问题才能用DP解决。

        其次就是大家比较习惯于背下来递推公式而不是真正的去理解了动态规划的内涵。也就是说，虽然递推公式非常的重要，但是动态规划也不是只有递推公式。

三、DP数组的含义

        DP数组（也就是状态数组）储存着所需要求解的问题的临时解或者中间结果，比如在背包问题中，dp[i][j]的含义可能是前i件物品放入容量为j的背包可以获得的最大价值。

四、递推公式

        递推公式（也叫状态转移方程）用于找到计算dp[i][j]时需要考虑的相关状态，同时给出了计算新状态的方法。例如，在背包问题中，状态转移方程可能是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) （其中w和v分别表示物品的重量和价值）。

五、DP数组的初始化

        DP数组的初始化往往对应着问题的底层情况。例如，在背包问题中，当背包的容量为0时，装入的物品价值总是0，因此我们初始化dp[i][0] = 0（其中0<=i<=n）。

六、DP数组遍历顺序

        DP数组的遍历顺序取决于递推公式。比如在以上的背包问题中，由于dp[i][j]与dp[i-1][j]和dp[i-1][j-w[i]]有关，因此我们需要按照i递增，j递增的顺序遍历DP数组。

七、打印DP数组        

        打印DP数组能有助于我们理解DP过程以及调试代码。通过循环遍历所有DP数组的元素并打印，我们可以看到DP的过程。

八、动态规划五部曲总结

1. 确定DP数组（DP table）以及下标的含义。
2. 确定递推公式。
3. DP数组如何初始化。
4. DP数组如何遍历，确定遍历顺序。
5. 确定如何返回结果。即由 DP 数组得到我们最终想要的答案。

如何排错

        最好就是将自己的DP数组打印出来，来判断其中的数值是否和我们的逻辑顺序一样。 

力扣题号：509. 斐波那契数 – 力扣（LeetCode）

注：下述题目和示例均来自力扣

题目

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示

• 0 <= n <= 30

思路

解法一：递归

        虽然这篇文章的最终目的是入门动态规划，但是我发现这道题真的也是一道很标准的可以使用递归的，题目，那么为什么不来尝试一下。

        首先是结束标志，也就是 n < 2的时候

        然后就是递归寻找 fib(n – 1) + fib(n – 2); 这个答案

        因为是为了动态规划而写的文章，在这里我就不过多的阐述了。

代码实现

class Solution {
    public int fib(int n) {
        if(n < 2){
            // 0 or 1
            return n;
        }
        // 递归调用
        return fib(n - 1) + fib(n - 2);
    }
}

不算快，但是你就说过没过吧。。。。。

解法二：动态规划

首先我们应该牢记，《动态规划五部曲》这么个过程。

（1）首先我们要确定一下dp数组下标及其含义

        dp[i]：由第 i – 1 和 i – 2个斐波那契数加和得到的第 i 个斐波那契数

（2）然后我们就要确定递推公式

        这是一道动态规划的入门题目，递推公式也是比较容易找到。因为它已经在题目出出现了。

（3）然后是初始化dp数组

        这有啥好说的，斐波那契数列列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。

   ,  

（4）然后是确定一下遍历的顺序

        我们这里因为 dp[i] 需要 i – 1 和 i – 2 ,所以很明显这是一个从前往后的顺序。

（5）最后是举例得到一个dp数组

        比如我们的 n = 8 ， 那么得到的 dp数组应该是如下：

代码实现

class Solution {
    public int fib(int n) {
        // < 2判断
        if(n < 2){
            return n;
        }
        // 使用动态规划
        // dp[i] = dp[i - 1] + dp[i - 2]
        int[] dp = new int[n + 1];
        // 初始化dp数组
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n ;i++){
            // 递推公式
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

真的很短，但是动态规划的思路还是要有。

结果来喽，超越了全世界的人！！！！！！！！！

不过还没结束

        发现了吗，我们根本就不需要其他的数据，因此这里创建的数组我们每次都只需要 i 的前两个数罢了，根本就不需要其他的数，因此我们可以使用如下的修改方式来节省内存的开销，达到一个遥遥领先的目的。

class Solution {
    public int fib(int n) {
        // < 2判断
        if(n < 2){
            return n;
        }
        // 使用动态规划
        // dp[i] = dp[i - 1] + dp[i - 2]
        // 使用两个数维护
        int dp0 = 0;
        int dp1 = 1;
        int res = 0;
        for(int i = 2; i <= n ;i++){
            // 递推公式
            res = dp0 + dp1;
            dp0 = dp1;
            dp1 = res;
        }
        return res;
    }
}

总结

        在处理动态规划的题目的时候，我们要按照整体的五步骤来进行处理。首先是确定dp数组下标及其含义，然后确定下来递推公式，再然后初始化dp数组，然后确定遍历顺序，最后举例推导出来dp数组即可。

        掌握下来，慢慢的进入动态规划的心吧❤。