一个讲得特别细（luo）腻（suo）的动态规划之入门

时间 2021-01-20 标签动态规划背包问题

//我其实早就想写一篇动态规划的文章了，虽然我也很弱……我的思路会和市面上的一些辅导书不同，我直接从背包问题入手，主要面对初学者，讲的比较啰嗦，还会涉及很多优化供学有余力者学习。一旦弄懂了这类比较典型也比较难的问题，动态规划的能力会显著提升。
文章里可能会有纰漏，希望大家帮我指出，但是请不要嘴臭

动态规划定义

~~没用，想看自行百度（滑稽~~

一些基本知识和dp（动态规划）的基本认识

- 最优化原理和无后效性原则

作为一个弱省蒟蒻，我的粗鄙的理解就是“现在要干的事对之前没有影响而且是最好的”，这也是符合我们的认知规律的。比如说，我们小学时有接触过一类题（当时虐的年幼的我死去活来）

小明的妈妈要看电视剧，所以小明必须艰苦创业自力更生（雾）。小明早上要干许多事，比如烧水，开电脑luogu签到，上厕所。烧水需要5分钟，上厕所需要2小时（真实），开电脑需要1小时，怎样安排用时最短？

首先，在生活中，现在做的事肯定不会影响过去（~~起码暂时不会~~ ），同样未来做的事也不会影响到现在，这就叫做无后效性原则。

那么什么是最优化呢？比如说我们已经开始烧水，那我们现在应该干什么呢，很显然是开电脑，这样我们上完厕所后水也烧好了，电脑也开了（~~痔疮也有了~~ ）。这就是最优化原理，我们只要最好的。

- 记忆化搜索

表面高大上，但是很多人在做水题的时候早就基本掌握这个思想了。

N！即1 * 2 * 3 … * N,现在，我们求99！，100！，101！怎么办呢？

显然（粗鄙之言），我们只需要算出99！，就不需要再从头计算了，因为100！即是99！ * 100。

如果我要求的是1！，2！…N！呢，并且要求在全部计算完之后输出答案？

显然（逃），我们需要开一个a[101]数组，去保存答案最后输出。这样的话，问题就简单了，我们求N！，只需要知道(N - 1)！，求（N - 1）！，只需要知道（N - 2）！ ……以此类推，我们只需要知道1！ = 1，我们便可以推出2！，进而推出3！……而不需要每次都从头计算。我们将算出的1！，2！……存入a数组，不仅要作为答案输出，还要继续使用它，就好像我们将1！……记下了一样，因此叫记忆化。

记忆化搜索中的dp思想

首先，求N！的过程是满足最优化和无后效性的，所以才能想到这道题可以用dp（虽然好像并没有明确的选择最优，但是我们由(N - 1）！得出N！时只有一个选择—— *N，我们别无选择♂时的唯一一个选择，就可以认为是最优的。

作为让OI选手头疼的拦路虎，状态设计和转移方程无数次令我自闭。其实，只要做题时勤于思考，这种思维方式是可以逐步形成的。

上述问题我们仅用了一层循环便解决了问题（仅仅举例，高精度等问题自己把控），既然说是dp，我们该怎样设计状态和书写转移方程呢？

在dp中，有种思想特别有用，这种思想叫做逆推（并不适用于所有题），这道题我们不妨逆推。

上文中，我们已设计好了状态（即由1！求2！进而求3！……），大概是下面这个样子的

进而状态转移方程也得到了：a[N] = a[N - 1] * N;