是的没错，这个文章能让你完全学会:

dynamic programming 动态规划

悄悄话:是的，学会动规，至于精通请前往👉

从图中可以看到，光是算fib(6)，就要重新算3遍fib(3)，时间复杂度就比较恶心了。对了，你想起什么没有？记住子问题的答案--动规登场！

1.子问题记忆法

使用一个数组来记录各个子问题的解，当再一次遇到这一问题的时候直接查找数组来获得解避免多次计算子问题。

//动规解决斐波那契(子问题记忆法) int fib(int a[],int n) {     if (n == 0)     {         a[0] = 0;         return 0;     }     if (n == 1)     {         a[1] = 1;         return 1;     }     if (a[n] >= 0)     {         return a[n];     }     a[n] = fib(a, n - 1) + fib(a, n - 2);     return fib(a, n - 1) + fib(a, n - 2); }

2、自底向上解决方案

先求解子问题再根据子问题的解来求解父问题，斐波那契数列的子问题图如下：

//动规解决斐波那契(自底向上解决) int fib(int a[],int n) {     a[0] = 0;     a[1] = 1;     for (int i = 2; i <= n; i++)     {         a[i] = a[i - 1] + a[i - 2];     }     return a[n]; }

自底向上的计算方法实现起来非常容易，分析算法，仅从形式上面分析算法可知，算法的时间主要消耗在计算数据规模为n的数组里面的数上面了，所以时间复杂度仅为:O(n)。递归在斐波那契的地位不保了！！

但是我们可以看到，在使用动规的时候，我们似乎多开了一个数组，那么空间是否会受到影响？答案是肯定的！但是在1000ms,256Mb的条件下，牺牲空间换取时间绝对是一笔很值的交♂易！

练习:LuoGu3986&钢条切割

---

3.动态规划的原理

最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

重叠子问题

在斐波拉契和钢条切割中，可以看到大量的重叠子问题，比如说在求fib(6)的时候，fib(2)被调用了5次。如果使用递归算法的时候会反复求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题性质。在动态规划算法中使用数组来保存子问题的解，问题多次求解的时候可以直接查表不用调用函数递归。

简单来说，动规就是递归再加上记录。

花小部分空间，省大部分时间。

4.动态规划的应用

4.1背包问题

1.零一背包

有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，每个物品只能选用一次,使得价值总和最大。

这是\color{blue}\text{最基础}最基础的背包问题，总的来说就是：选还是不选

例题:LuoGu1048

显然，这道题并不能用贪心，因为假设你要在100时间内采药，有三个药：71时间，89价值；30时间，44价值；40时间，45价值。如果是贪心，就会果断选(71,89)，但事实上(30,44)和(40,45)更优。此时请出动规，怎么用呢？

列出状态转移方程!

状态转移方程的概念可以自行百度，在这里不做过多讨论。

对于一个物品，只有两种情况

1.第i件不放进去，这时所得价值为:dp[i-1][v]

2.第i件放进去，这时所得价值为:dp[i-1][v-c[i]]+w[i]

故状态转移方程为:

dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]]+c[i])

注:零一背包可以用一维数组记录最优计划dp[v],表示不超过v体积的最大价值。

巨佬们看过来！！背包退火👈了解一下？

2.完全背包

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

完全背包和01背包十分相像， 区别就是完全背包物品有无限件。总的来说就是选还是不选，选几件。

例题：LuoGu1616

关键字：