漫画：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方程不同。

原文链接：

https://mp.weixin.qq.com/s/-bngVVU3O1HaXJDnLYbUgg

(*本文为 AI科技大本营转载文章， 转载请联系作者 )

◆

福利时刻

◆

入群参与每周抽奖~