漫画：5分钟了解什么是动态规划？
作者 | 调皮的阿广
来源 | 视学算法（ID：z872561826）
动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。
注意：动态规划往往使用表格来存储中间结果
注意：每一步上几层台阶，都是一个决策问题！
说到这里，阿广你有没有发现几点问题？
1、将求F（10）这个问题，完美的分解成了F（9）和F（8），找到了局部的最优解，与贪心算法有点像呀。
2、既然F（10）=F（9）+F（8），那么F（9）=F（8）+F（7），依此类推，最终问题被逐渐降低了规模，越来越简单，这也是分治算法的思想。
动态规划的三要素：
1、最优子问题
F（10）=F（9）+F（8），就是F（10）问题的最优子问题，局部的贪心完美的将问题分解，如果得到的F（9）和F（8）都是最优解，那么F（10）一定也是最优解了。
2、边界条件
分解到最后，一定是变成了规模最简单的问题，即F（1）和F（2），这两个问题不能再分解了，不过没关系，他们很简单，用你的小心心算就ok了。
3、状态转移方程（DP方程）
本问题的状态转移方程为：F（n）=F(n-1)+F(n-2)，这就是解决问题的核心，使得状态能够“动”起来。
注意：相同颜色的部分代表相同的结果
可以看出来，动态规划算法的核心是DP方程。
所以说，状态转换方程（DP方程）就是算法的核心，那么设计DP方程，要有什么注意的呢？以下列出来几点！
1、最优化子问题
从上面的算法三要素中，可以看出，DP方程是最优子问题中归纳而来的。那么，什么才算“最优子问题”呢？就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前的基础上最优。具体的说，我们默认F（8）和F（9）就是最优的，在此基础上，得到最优的F（10）。
2、不影响后续决策
由于上一条我们看到，如果F（8）的决策会影响到F（9）和F（10）的决策，那么F（10）=F（9）+F（8）就不成立了，所以，要一定保证，每个阶段的决策仅受之前决策的影响，但不影响之后阶段的决策。
典型应用1---01背包问题
01背包问题的决策，就是判断第i件物品，装还是不装，哪种决策总价值最大？
那么，我们是否能够定义状态为s[i]呢，用来表示第i件物品决策的最大价值？
答案是不可以的，因为这个状态会影响到后面的决策，换种说法讲，装不装入一个物品，会影响到背包中的剩余空间，所以后面的决策当然会受影响。
典型应用2---最长公共子序列问题（这一问题常被用于比较“相似度”）
决策方式就是判断str1[i]和str2[j]的关系，关系不同，则DP方程不同。
原文链接：
◆
福利时刻
◆
入群参与每周抽奖~
扫码添加小助手，回复：大会，加入福利群，参与抽奖送礼！