是的没错，这个文章能让你完全学会:
dynamic programming 动态规划
Content
1. 从乘方和谚语说起
2. 斐波那契数列：递归受到了挑战
3. 动态规划的原理
--3.1最优子结构
--3.2重叠子问题
4.动态规划的应用
--4.1背包模型
--4.1.1 零一背包
--4.1.2 完全背包
--4.1.3 多重背包
--4.2线性动规
--4.3区间动规
5.入土
提示:如果你对动规已经有所了解，请直接进入3或4
1.从乘方和谚语说起
相信你们都学习过乘方，那么我们知道:
2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 =2^10=1024
那么2^11是多少呢？你会自然而然地答出2048!
好的，祝贺你已经学会了动规初步！
为什么？
我们作为人，计算2^11自然不是2X2……X2=2048这样算的
而是通过已经给出的2^10=1024计算的：2X1024=2048。
这个过程就包括了动规的核心思想之一：
记住子问题的解。
一句谚语解释：
Those who cannot remember the past, are doomed to repeat it.--George Santayana
那些忘记过去的人注定要重蹈覆辙。
在编程中，动态规划通过记住子问题的解，能够以高效率低耗时而脱颖而出，成为最热门的算法之一（详见2）。
动规的概念可以自行百度，在这里不做过多讨论。
2. 斐波那契数列：递归受到了挑战
对于斐波那契数列的求解，递归往往是最先考虑的解法，但是在1000ms的苛求下，递归O(2^n)的时间复杂度就比较麻烦了。
//递归解斐波那契
long long Fib(long long n)
{
if (n==1||n==2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
图解👇
![[学习记录]Dynamic Programming从入门到入土-LMLPHP]( "[学习记录]Dynamic Programming从入门到入土-LMLPHP")
从图中可以看到，光是算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的条件下，牺牲空间换取时间绝对是一笔很值的交♂易！
3.动态规划的原理
最优子结构
用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。
重叠子问题
在斐波拉契和钢条切割中，可以看到大量的重叠子问题，比如说在求fib(6)的时候，fib(2)被调用了5次。如果使用递归算法的时候会反复求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题性质。在动态规划算法中使用数组来保存子问题的解，问题多次求解的时候可以直接查表不用调用函数递归。
简单来说，动规就是递归再加上记录。
花小部分空间，省大部分时间。
4.动态规划的应用
4.1背包问题
1.零一背包
有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，每个物品只能选用一次,使得价值总和最大。
这是\color{blue}\text{最基础}最基础的背包问题，总的来说就是：选还是不选
显然，这道题并不能用贪心，因为假设你要在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背包十分相像， 区别就是完全背包物品有无限件。总的来说就是选还是不选，选几件。
列出状态转移方程!
若不采这种草药，则时间花费没有增多,经过的 草药种数增加了1,采到草药价格不变,所以 dp[i][j]=dp[i-1][j];
若采这种草药,则 时间花费增加了t[i],种数增加1,采到草药价格增加了p[i],所以 dp[i][j]=dp[i-1][j-t[i]]+p[i]。
我们要使dp[i][j]\color{red}\text{尽可能大}尽可能大,即👇
dp[i][j]=max(dp[i-1][j],f[i-1][j-t[i]]+p[i])
这道题对于药就没有限制了，每种都无限多，所以优化出现了：
当一个药品的价值小于另一个药品的价值，并且时间高于另一个药品，我们就可以不去考虑这个药品。既然我们不是地主家的傻孩子，为什么还要花更多的时间采更少价值的药呢😂?
注:该问题也可以压缩到一维最优计划dp[v],我们可以将药的种类i省略 ，用后面算的值覆盖掉前面算的值.
巨佬们，背包退火👈了解一下？
3.多重背包
有N种物品和一个容量为V的背包。第i种物品有n[i]个可用，每件费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这里又多了一个限制条件，每个物品规定了可用的次数。
没错，对于一般的多重背包，换成01背包水就行了，至于不一般的嘛……
列出状态转移方程!
f[i][v]=max(f[i-1][v-k*w[i]]+ k*c[i]|0<=k<=n[i])
4.2线性动规
其实线性动规是动规中较简单的一类题目，重点有三：
1.选对算法，正确维护
2.巧妙利用前缀和
3.别忘了合理递推
线性递归的题个人觉得要多练，所以放了几道题，希望在刷题的过程中，你能够领悟其精髓。同时，你可以参考一个近乎万能的线性模板博客👉线性动态规划
4.3区间动规
典型的区间模型，回文串拥有很明显的子结构特征，即当字符串s是一个回文串时，在X两边各添加一个字符'a'后，a s a仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有
d[i][j] = d[i+1][j-1]
这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0；
当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：
1.在A[j]后面添加一个字符A[i]；
2.在A[i]前面添加一个字符A[j]；
列出状态转移方程!
d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1;
//每次状态转移，区间长度增加1
撒花✿✿ヽ(°▽°)ノ✿
诶Σ( ° △ °|||)好像忘了点什么？
5.入土
如题所述，动态规划在时间上远胜递归，在通用性上远胜贪心，但是它毕竟只是个算法，不是自动AC机，接下来我们简单的谈谈它的缺点：
1.它节省时间的代价是浪费空间
这一点算是比较弱的缺点了，因为它有时开的空间只是九牛一毛，不值一提。但是！！在解决二维地图题中，要开一个dp[10000][10000]就会比较吃力。
2.它需要具体问题具体分析
不像贪心或者递归，dp是基本不具有模板的（最长单调子序列模板别吵吵），而且在打dp之前，要仔细思考，因为号称具有全局最优解的动规有可能让你失去人生中美好的1.5小时。
3.它的状态转移方程需要考虑
再确认要用dp一头磕死在一道题上之后，必须要做的就是确认子问题之间的关系，并且由题意得出找出全局最优解的状态转移方程，如果找不出来，那么就应该及时更换方法。
4.dp并不是不需要优化
向其他的大部分算法一样,dp也是需要优化的，但是优化往往又让人无从下手，搜索可以剪枝，但dp就不一定行了。比如上面的疯狂采药问题，我们才能就提论题地进行优化。那么dp有没有具有普遍性的优化呢？有的！往往，我们可以对dp通过滚动数组省空间、压缩一维省时间、状态压缩二进制、矩阵优化转问题、线段树优化区间、树状数组O(logn) etc.
写了一下午，感觉写完自己已经先一步入土惹……
撒花✿✿ヽ(°▽°)ノ✿