简介

动态规划？

动态规划，DynamicProgramming，其中这个 Programming 可并不是指的计算机编程，而是一种表格法（线性规划也是这样滴）。首先我们来看一看 Wikipedia 上动态规划的定义：

Dyanmic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. 动态规划是一种通过将问题分解为一堆较简单的子问题，逐个解决它们并将结果存储下来从而利用这些结果解决复杂问题的方法。

简单地说，动态规划就是一种分治+以空间换时间的思想。在具体实现上，动态规划算法通常基于一个动态转移方程及一个或多个初始状态，而当前子问题的解将由上一次子问题的解推出。

状态？转移方程？

状态指的就是子问题。就好比我们需要求斐波那契数列的第$n$ 项，直接面对这个问题我们很可能会感到无从下手。但是，如果我们能够直到第 $n - 1$ 项和第 $n - 2$ 项这个问题就迎刃而解了。在刚才的例子中，第 $n$ 、$n - 1$ 、$n - 2$ 就是这个问题的某三个状态。很显然由 $n - 1$ 和 $n - 2$ 两个状态可以通过直接相加推出 $n$ 这个状态，所以我们就得到了问题的状态转移方程：

$$f(n)= f(n - 1) + f(n - 2)$$

但是光有转移方程还是不够的，我们还需要找到这个问题的初始状态。不妨把初始状态理解为最简单、最根本的状态。在刚才提到的这个斐波那契问题中初始状态显然为：

$$f(1)= 1, \ f(2) = 1$$

以空间换时间？

继续来看上一个例子。在上一个例子中如果我们直接采用分治而不存储子问题的解的话，我们相当于计算每一项的时候都要从第一项开始推导。显然，在此之中我们进行了大量的重复计算。但是如果我们把已经计算出来的每一项都存储下来的话，我们就不必要每一项都从第一项开始推了，直接调用存储内已经被算好的前两项的结果即可。这样就为我们节省了大量的时间。

适用范围？

很显然，动态规划这一算法仅仅适用于子问题重叠的情景。也就是说，不同的子问题都具有公共的子子问题（自问题的求解是递归实现的，故我们可以一直将子问题划分为子子问题直到它变为最简单的情形）。试想，如果子问题并不重叠，那么计算出的子问题的解并不能被多次利用，那么存储下它们将会是毫无意义的。

如何动态规划？

1.找到复杂问题的子问题（设计状态）；2.推导子问题与子问题之间的递推关系（如何转移状态）；3.找到并解决最简单的子问题（确定边界）。

一维动态规划

我们不妨从最简单的一类动态规划开始（在很多地方也把这类问题称作递推问题）。

这类问题的简单之处就在于每一个阶段的状态是唯一的，并且下一个阶段的状态可以由之前若干个状态直接得到。因此，解决这类问题所需的时间复杂度级别是$\mathcal{O}(N)$ 。

下面，我们就来领略几类经典的一维动态规划问题。

平面分割问题

直线分割平面

用$n$ 条直线分割一个无限大的平面，最多可将该平面分成几个区域？

---

首先，我们先来考虑最简单的情况。当$n = 1$ 时，很容易得出 $f(1) = 2$ 。

接下来考虑已有$n - 1$ 条直线的情况。如果此时再添加一条直线，若要分出最多的区域，那么新加的直线必然要与已有的$n - 1$ 条线相交。自然便会产生 $n - 1$ 个新交点，产生$n$ 条新线段，整个平面也就多了 $n$ 个区域。

由此分析，我们不难得出状态转移方程：

$$f(n)= f(n - 1) + n$$

化简后也可以得到：

$$f(n)= \frac{1}{2}n(n + 1) + 1$$

很简单是不是？下面我们不妨来看看此问题的升级版—— 折线分割平面。

折线分割平面

HDUOJ- 2050: 折线分割平面

---

类似地，首先我们不难得出$f(1) = 2$ 。

在已有$n - 1$ 条折线时再添加一条折线，若要分出最多的区域，那么新加折线的每一条边必然要与已有的 $n - 1$ 条折线的共 $2(n - 1)$ 条边相交，产生 $2(n - 1)$ 个新交点。所以，新加入的折线一共就会带来 $4(n - 1)$ 个新交点，产生 $4(n - 1) + 1$ 条新线段（点与段的关系），自然也就会新增 $4(n - 1) + 1$ 个区域。

为了更好地演示这一思想，不妨看看下图中对于$f(1)$ 到 $f(2)$ 转移的演示：

由此分析，我们不难得到状态转移方程：

$$f(n)= f(n - 1) + 4(n - 1) + 1$$

化简后也可以得到：

$$f(n)= 2n^2 - n + 1$$

思考：刚才折线是有两条线段组成的（“V” 字形），那我如果改成三条线段组成的折线（“Z” 字形，其中 “Z” 的两端看成平行的射线）呢？

$$f(n)= f(n - 1) + 9(n - 1) + 1$$

思考：如果改成$k$ 条线段组成的折线呢？

我们很容易发现，在解决由$k$ 条线段组成的折线分割平面时都遵循如下思路：

1. 当 $n = 1$ 时，无论 $k$ 取何值，都有 $f(1) = 2$ ；
2. 一条直线最多可与 $k$ 条线段组成的折线（两端平行）产生 $k$ 个交点；
3. 当已有 $n - 1$ 条折线时再添加一条折线，若要使分割的区域最多，新加入的折线的每一条边必然要与已有的 $n - 1$ 条折线共$k(n - 1)$ 条边相交，产生 $k(n - 1)$ 个新交点。所以，新加入的折线便会带来 $k^2(n - 1)$ 个新交点，产生 $k^2(n - 1) + 1$ 条新线段，自然也就会新增 $k^2(n - 1) + 1$ 个新区域；
4. 那么就很容易得出状态转移方程：

$$f(n)= f(n - 1) + k^2(n - 1) + 1$$

P.S.怎么莫名感觉挺像数学归纳法的，23333~

封闭图形分割平面

三角形分割平面

HDUOJ- 1249: 三角形

---

类似地，首先我们不难得出$f(1) = 2$ 。

在已有$n - 1$ 个三角形的基础上再添加一个三角形，若要分出最多的区域，新加三角形的每一条边都要与已有的 $n - 1$ 个三角形相交，产生 $2(n - 1)$ 个新交点。所以，新加入的三角形一共就会带来 $6(n - 1)$ 个新交点。唯一不同的地方是，相对折线分割平面，这里是封闭图形分割平面，所以 $6(n - 1)$ 个交点会带来 $6(n - 1)$ 个新线段，自然也就会新增 $6(n - 1)$ 个新区域。

由此分析，不难写出状态转移方程：

$$f(n)= f(n - 1) + 6(n - 1)$$

化简后也可以得到：

$$f(n)= 3n(n - 1) + 2$$

思考：那对于矩形分割平面呢？

$$f(n)= f(n - 1) + 8(n - 1)$$

思考：那对于$k$ 边形呢？

我们很容易发现，在解决$k$ 边形分割平面问题时都遵循以下思路：

1. 当 $n = 1$ 时，无论 $k$ 取何值，都有 $f(1) = 2$ ；
2. 对于该 $k$ 边形，记一条直线可与其产生的最大交点个数为 $m$ （对于凸 $k$ 边形，恒有 $m = 2$ ）；
3. 当已有 $n - 1$ 个 $k$ 边形时再添加一个 $k$ 边形，若要使分割出的区域最多，新加入的 $k$ 边形的每一条边必然要与已有的 $n - 1$ 个 $k$ 边形产生 $m(n - 1)$ 个新交点。所以，新加入的 $k$ 边形一共会带来 $km(n - 1)$ 个新交点，它们会产生 $km(n - 1)$ 条新线段，自然也就会新增 $km(n -1)$ 个新区域；
4. 那么就很容易得出状态转移方程：

$$f(n)= f(n - 1) + km(n - 1)$$

圆形分割平面

用$n$ 个圆分割一个无限大的平面，最多可将该平面分成几个区域？

---

类似地，首先我们不难得出$f(1) = 2$ 。

在已有$n - 1$ 个圆时再添加一个圆，若要使分割出的区域最大，则这个圆应与已有的 $n - 1$ 个圆各有两个交点。所以新加入的圆便会带来 $2(n - 1)$ 个新交点，带来 $2(n - 1)$ 个新线段，自然也就会新增 $2(n - 1)$ 个新区域。

由此分析，不难写出状态转移方程：

$$f(n)= f(n - 1) + 2(n - 1)$$

化简后也可以得到：

$$f(n)= n^2 - n + 2$$

在搞清楚了二维平面的分割问题后，让我们来试试三维空间的分割？

平面分割空间

HDUOJ- 1290: 献给杭电五十周年校庆的礼物

---

通过刚才的分析，我们不难发现，二维平面的分割与线与线之间的交点有关。那么三维空间的分割会不会与面与面之间的交线有关呢？

类似地，首先我们不难得出$f(1) = 2$ 。

在已有$n - 1$ 个平面时再添加一个平面，若要使分割出的空间最多，那么这个平面必然与已有的 $n - 1$ 个平面各存一条交线。所以新加入的平面便会带来 $n - 1$ 条新交线。回想前文讨论过的直线分割平面，$n$ 条直线最多可将平面分为 $g(n) = \frac{1}{2}n(n + 1) + 1$ 个区域，不难得出这 $n - 1$ 条新交线最多可将新平面分为 $g(n - 1) = \frac{1}{2}(n - 1)n + 1$ 个区域，自然该空间也就新增了 $g(n - 1) = \frac{1}{2}(n - 1)n + 1$ 个区域。

由此分析，不难写出状态转移方程：

$$f(n)= f(n - 1) + g(n - 1) = f(n - 1) + \frac{1}{2}(n - 1)n + 1$$

小结

-对于分割平面，若要使分割出的区域最多，那么进行每一次分割时都要确保新加入的图形与已有的图形存在数量尽可能多的交点。继而，我们可以通过新增交点个数、新增线段个数和新增区域个数之间的关系得出第 $n$ 次分割最大新增区域个数与 $n$ 之间关系式 $k(n)$ ，也就很容易可以写出状态转移方程 $f(n) = f(n - 1) + k(n)$ 了。-对于分割空间，若要使分割出的区域最多，那么进行每一次分割时都要确保新加入的平面与已有的平面存在数量尽可能多的交线。同时，这些交线应将新加入的平面分成尽可能多的部分。记直线分割平面的公式为 $g(n)$ ，便可很容易地写出状态转移方程：$f(n) = f(n - 1) + g(n - 1)$ 。

另外，我们不难发现这其实是最为简单的一类递推问题—— 第 $n$ 个状态仅仅由第 $n - 1$ 个状态这一个状态决定。下面，我们不妨来看看第 $n$ 个状态需要由之前的多个状态决定的递推问题。

简单的铺砖问题

HDUOJ- 2046: 骨牌铺方格

---

我们依然先从简单的问题分析起。当长$n = 1$ 时，很容易发现只有一种铺法，即 $f(1) = 1$ 。当长 $n = 2$ 时，也很容易发现有两种铺法，即 $f(2) = 2$ 。

接下来我们来看看通用的情况。$f(n)$ 可以由哪些途径得来呢？第一种途径，便是在 $f(n - 1)$ 的基础上再加上一块竖着摆放的骨牌便可以得来。第二种途径，便是在 $f(n - 2)$ 的基础上再加两块横着摆放的骨牌得来。为什么这里两块骨牌不能竖着放呢？小傻瓜，这种情况不是包含在第一种途径里了吗？所以说，当我们在推到状态转移方程的时候一定要做到既不遗漏，也不重复。

由上分析，不难得出状态转移方程：

$$f(n)= f(n - 1) + f(n - 2)$$

环形染色问题

HDUOJ- 2045: 不容易系列之(3)—— LELE的RPG难题

---

我们依然先分析最简单的情况。当$n = 1$ 时，既然只有 3 种颜料，那么自然只有 3 种染色方案；当 $n = 2$ 时，这两个区域染的颜色显然应该是不一样的，所以根据乘法原理，染色方案的种数为 $3 \times 2 = 6$ 种。

怎样才能获得一个长度为$n$ 的合法染色方案呢？我们先来看看长度为 $n - 1$ 的方案，它有合法合不合法两种可能。我们来思考对于不同状态的长度为 $n - 1$ 的方案，怎样加入最后一种颜色才能使得得到的长度为 $n$ 的染色方案合法。

如果长度为$n - 1$ 的方案本身合法，那一定就意味着它首尾两格颜色不同。在这种情况下若要向末尾再添加一种颜色就只有一种选择了，故种数为 $1 \times f(n - 1)$ 种。

如果长度为$n - 1$ 的方案不合法，有没有可能加上一种颜色后就变合法了呢？不难发现，只有当其除首尾颜色相同外其它部位均合法时，在末尾添加一种与首尾颜色不同的颜色就合法了。除首尾颜色相同外其它部位合法的长度为 $n - 1$ 的方案显然有 $1 \times f(n - 2)$ 种，此时向末尾添加颜色可有两种选择，故种数为 $2 \times f(n - 2)$ 种。

但是注意，这里有一个细节问题：当$n = 3$ 时，长度为 $n - 2 = 1$ 的方案显然是不满足首尾颜色不同的（因为首尾都是同一个点），所以 $f(3)$ 也是需要另外预先算出来的。不难发现，此时我们也必须保证三个方块颜色互不相同，故由乘法原理：$f(3) = 3 \times 2 \times 1 = 6$ 。

由上分析，不难得出状态转移方程：

$$f(n)= f(n - 1) + 2f(n - 2)$$

思考：那如果有$k$ 种颜色可选呢？

首先，我们来思考一下$f(1)$ 和 $f(2)$ ：

• 当 $n = 1$ 时，我们显然只有 $k$ 种颜色选择，故 $f(1) = k$ ；
• 当 $n = 2$ 时，两个方块的颜色显然应该不同，故 $f(2) = k(k - 1)$ ;
• 当 $n = 3$ 时，三个方块的颜色应当互不相同，故 $f(3) = k(k - 1)(k - 2)$ 。

接下来对于$n > 3$ ，利用刚才的思路不难得到状态转移方程：

$$f(n)= (k -2)f(n - 1) + (k - 1)f(n - 2)$$

路线个数

HDUOJ- 2563: 统计问题

---

这道题看起来很像搜索啊……但是其中有一重要的特性就是不能往后走，直接导致了每个阶段只有一种状态，于是就可以用递推了。

阅读题意后我们很容易发现，第$n$ 步可选的走法事实上是与第 $n - 1$ 步有关的。如果第 $n - 1$ 步是向左或向右移动，那么第 $n$ 步就只有两种走法（因为不能往回走）；而如果第 $n - 1$ 步是向上移动，那么第 $n$ 步也就有一定三种走法了。

也就是说，当你走到第$n - 1$ 步时，你无论如何都至少有两个选项可以走，这就是 $2f(n - 1)$ 种方案。但是对于第 $n - 1$ 步是向上走的情况我们少算了一种方案。第 $n - 1$ 是向上走的情况显然有 $1 \times f(n - 2)$ 种，所以就很容易写出状态转移方程：

$$f(n)= 2f(n - 1) + f(n - 2)$$

排列问题

复杂的排列问题

HDUOJ- 1297: Children’s Queue

---

对于有$n - 1$ 位同学的情况，新加入的第 $n$ 位同学只可能是 M 或者 F

对于末尾为M 的情况： 若 $f(n - 1)$ 合法，那么在末尾加入一位 M 后形成的 $f(n)$ 一定是合法的；而如果 $f(n - 1)$ 不合法，就算在末尾加上一位 M 也不能改变有女孩子单身的事实。故末尾为 M 的 $f(n)$ 有 $f(n - 1)$ 种。

对于末尾为F 的情况： 如果在 $f(n - 1)$ 末尾能够加入 F，必然意味着 $f(n-1)$ 的最后一位也为 F。这种情况事实上也等效于在 $f(n-2)$ 末尾加入 FF。如果 $f(n-2)$ 本身合法，那么在末尾加入 FF 后形成的 $f(n)$ 必然也合法；而如果 $f(n - 2)$ 不合法，存在 $f(n - 2)$ 末两位为 MF 的情况，加上 FF 后形成的 $f(n)$ 后四位为 MFFF，是合法的。 这种情况事实上也等效于在任意合法的 $f(n - 4)$ 末尾添加 MFFF，所以末尾为 F 的 $f(n)$ 有 $f(n - 2) + f(n - 4)$ 种。

根据上述分析，很容易得出递推公式：

$$f(n)= f(n - 1) + f(n - 2) + f(n - 4)$$

错排问题

全错排问题

HDUOJ - 1465: 不容易系列之一

---

某人写了$n$ 封信将它们装入 $n$ 个信封，但愚蠢的他把所有信都装错了信封，那么这个人有多少种蠢法…… 这就是著名的伯努利-欧拉的装错信封问题。

我们还是先从最简单的情况看起吧。当$n = 1$ 时，想装错都没法装错 ┑(￣Д ￣)┍，不难得出 $f(1) = 0$ 。当 $n = 2$ 时，也很容易得出只有一种全错的方法，即 $f(2) = 1$ 。

我们再来试着看看通用的情况。假设现在已有装好的$n - 1$ 封信，那么它将有两种状态：已经是全错排或者还不是全错排。而我们需要做的，仅仅是加一封信进去。显然，新加入的这封信并不能被放在正确的信封里，所以我们需要从前 $n - 1$ 个信封中挑出一个，将新信放进去，并将信封中原来的信放入新信封中。

如果这$n - 1$ 封信已经是全错排，那么新加入的第 $n$ 封信可以装到这 $n - 1$ 个信封中的任意一个信封里去（同时把该信封里原有的信装在第 $n$ 封信的信封内）。由于前 $n - 1$ 封信中的任意一封信装在第 $n$ 个信封中一定是错误的，故这样生成的 $f(n)$ 一定也是全错排。易得这种情况共有 $(n - 1)f(n - 1)$ 种。

如果这$n - 1$ 封信还并不是全错排，那么那种情况下仅仅新加入一封信就能使其成为全错排呢？很显然，只有当这 $n - 1$ 封信中有且仅有一封正确是才有可能在新加入一封信的情况下使其成为全错排。我们不不妨记前 $n - 1$ 个信封中装了正确信件的是第 $M$ 个，那么我们只需要将新加入的第 $n$ 封信放入第 $M$ 个信封，将第 $M$ 个信封里原有的信件放入新的第 $n$ 分信封里就可以生成新的全错排了。那么 $n - 1$ 封信中有且只有一封被装在了正确的信封中有多少种情况呢？我们先去掉这封放了正确信的信封，剩下 $n - 2$ 封信不就是全错排吗？显然，有 $f(n - 2)$ 种情况。而这封放了正确信的信封可以是前 $n - 1$ 中的任意一个，易得这种情况共有 $(n - 1)f(n - 2)$ 种。

由此分析，不难写出状态转移方程：

$$f(n)= (n - 1)\left[ f(n - 1) + f(n - 2) \right]$$

刚刚这个人真是蠢出了风格。不过，虽然正常人难以蠢到这种地步，但还是难免可能装错$n$ 封信中的 $m$ 个。那么这种情况又该如何计算可能的种数呢？

部分错排问题

HDUOJ- 2049: 不容易系列之(4)——考新郎

---

某人写了$n$ 封信将它们装入 $n$ 个信封，但愚蠢的他把其中 $m$ 封信装错了信封，那么这个人有多少种蠢法……

很显然，去对于那装错了信封的$m$ 封信，不就是全错排问题吗…… 记 $g(m)$ 为有 $m$ 封信时全错排的种数，那么结合排列组合的相关知识很容易得到：

$$f(n)= C_{n}^{m} \times g(m)$$

小结

• 动态规划是解决具有子问题重叠这一特性的一类问题的方法。
• 一维动态规划问题每个阶段状态唯一，且下一个状态可以由若干个之前的状态直接得到。
• 写状态转移方程式时需要做到不遗漏且不重复。

%%%

• HDUOJ
• 刘春英老师 - ACM程序设计：递归求解
• Stanford - CS97SI - 04 Dynamic Programming
• 王勐 - 什么是动态规划？动态规划的意义是什么？
• 2Enstein_Jun - 平面分割，空间分割问题（递推关系）