动态规划与状态设计

        这一篇文章谈谈动态规划(Dynamic Programming， DP)。本材料中大量地出现动态规划类题目，这里做一个总结。
        动态规划是一种解决多阶段决策问题的高效算法设计思路，它的本质是分治思想。对于一个问题，它通常由若干子问题组成，解决了这些子问题，原问题也迎刃而解。例如树这种数据结构，它的分枝仍是一棵树，又如将区间分割，得到的仍是一个区间…很多事物都满足这种性质，可以考虑用DP思路解决。

        下面介绍一些DP术语。

• 状态。当前阶段所面临的客观条件称为一种状态。状态需要一定的量去描述，称为状态变(参)量。同时状态也拥有一定的值，称为状态量。
• 状态转移。状态可以视为一个问题，它由若干子问题构成，这些子问题也是一个个状态。由当前状态到它的子状态的过程称为状态转移。转移的数学表达式称为状态转移方程。
• 无后效性。每一个状态都是客观的。一个状态所对应的问题可能是多个不同问题的子问题，但是无论它从哪一个状态转移过来，这个状态都应该是客观独立的，它的任何属性都不会随受前一个状态的影响。这种性质称为无后效性，能用DP解决的问题必须满足无后效性。
• 最优化原理。一个问题是最优的，它的子问题必然也是最优的。

        用DP解决问题实际上就是设计合适的状态，列出对应的状态转移方程。DP的重点在于看清问题和子问题以确定状态，状态的设计是很重要的，它必须满足以下几点要求:

• 状态参量到状态量是一个多数值到单数值的映射，也就是说，每一个状态必须是确定的，唯一的，并且满足无后效性。
• 状态必须是可转移的，也就是能够列出明确的状态转移方程。

        下面思考这样一个题目，来认识状态设计:

题目描述

        2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，称基地A到基地B的距离为d。
        由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。
        你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

输入输出格式

输入格式：

        输入文件的第一行为n （n<=1000），表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。

输出格式：

        输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

        题目实质上是给定一棵树，其中一个选定的点可以覆盖两层的其余顶点，求覆盖整棵树的选点最小值。
        一个显然的状态设计思路是令f(x)表示以x为根的子树的选点最小值。这样做状态的确是唯一的并且有明确的值，但是它无法列出状态转移方程。
        但是，f(x)=$\sum f(k)$(k表示x的子节点)是否成立呢?显然不可，这是因为即使每一个子树都被覆盖掉了，根节点x也可能没被覆盖到;同时，每一个子树的选点覆盖范围可能有所包含，使得全局仍可以删掉几个点，结果不最优。
        这样的状态设计显然是失败的，问题便出在状态描述不清上。
        有时状态虽唯一，但是无法转移，就需要增加状态描述量来细化状态。
        首先认识到一个事实，原问题满足某种性质时，往往意味这它的子问题也要满足某种性质。
        如果定义f(x，y)表示根节点为x的子树，在满足性质P(y)的前提下最小选点数。P定义如下:

• P(0):子树完全被覆盖，且根节点被选。
• P(1):子树完全被覆盖，子节点被选。
• P(2):子树完全被覆盖，孙子节点被选。

        子树被完全覆盖仅有这三种状态

• P(3):所有子节点及其子树都被覆盖，但根节点未知。
• P(4):所有孙子节点及其子树都被覆盖，但根节点和子节点未知。

        其实还可以有P(5):所有孙子节点的子节点及其子树都被覆盖，但根节点子节点，孙子节点未知。但之后可以看到这种状态不参与转移，是无用的。仅这样就是可以转移的。
        若原树满足P(0)，则根节点向下两层(儿子和孙子)都一定被覆盖，但是倘若全树都被覆盖，所有子树都必须满足其孙子节点及其子树都被覆盖的性质。发现P(0~4)都符合条件，可以证明其余的任何状态都不符合，又发现全树的选点数是所有子树上选点数加一，于是有:

$$f(x，0)=\sum(min\{f(k，0...4)\})+1$$

        对于每一个子树，取其五个性质中选点最少的一个，这样既满足性质又能使解最优。这样直接作和是不会出现漏选多选的情况的。这是因为，子树都满足了需要的性质，全树一定可以完全被覆盖，不会缺选;同时，由于每一个子树都是满足性质的，并且选的是最小值，其余状态又不能使性质成立，删掉一个点必然使性质不再成立，所以不会多点。
        若原树满足P(1)，则根节点下一层全被覆盖，此时因为全树都被覆盖，所有子树都必须满足其子节点和子树都被覆盖的性质(即P(0~3))，被选的点满足P(0)性质。所以有:

$$f(x，1)=\min\{f(k，0)+\sum (\min\{f(k’，0...3)\})\}，k是任意子节点，k’是剩余的子节点$$

        理解同上。
        同理可得:

$$f(x，2)=\min\{f(k，1)+\sum (\min\{f(k’，0...2)\})\}，k是任意子节点，k’是剩余的子节点\\ f(x，3)=\sum (\min\{f(k，0...2)\})\\ f(x，4)=\sum (\min\{f(k，0...3)\})$$

        这种转移方法称为性质转移，它的原理是当原问题满足状态指定的某种性质时，其子问题也要满足特定的性质，这时原问题状态可以转移到所有满足特定性质的子问题状态。这里给出的五个状态就是所有满足的状态，少一个都会难以转移。
        另一种转移方式即为决策转移，它的原理通常是不同的决策，例如背包问题。本题用决策转移很难列方程。

        为了更好地理解状态设计，来重新认识一下01背包问题这种经典DP问题。本材料第2题就是这类问题。
        01背包属于决策转移型，决策是选不选当前的这个物品。
        当从所有物品中随机拿出一个时，如果背包可以装下的话，便会面临选还是不选的问题，这便是一个决策。规定物品全集为S，拿出的物品为x，物品i价值为w_i，则两种决策得到的价值分别为:

选该物品:w_x+?
不选该物品:0+?

        这里的?表示后面加上的价值暂时无法确定。但是注意到，如果选了该物品，对于剩下的物品集合S-{x}与原问题集合S，它们的问题本质上是同一类问题，都是从一个集合中取一些物品使价值总和最大，不选与之同理。这样就把问题拆成了两个本质相同的子问题。同时子问题最优时，原问题才最优，这是显然的。
        于是定义dp(Q)表示对于集合Q，从中拿走若干个物品得到的价值最大值。但是很快便发现，这其中忽略了物品体积的问题，物品体积显然会影响决策(太大时一定不能选)，并且这样描述状态并不能唯一地确定状态。于是应定义dp(Q，p)表示背包容量为p时，从集合Q中拿走若干物品得到的价值最大值。
        那么就有关系(vi表示物品i的体积):

$$若p\geq v_x时:dp(Q，p)=\max\{dp(Q-\{x\}，p)，dp(Q-\{x\}，p-v_x)+w_x\}$$

        这里从不选和选中取一个较大值。

$$p<v_x时，dp(Q，p)=dp(Q-\{x\}，p)$$

        这时，x无法被选择。
        这就得到了状态转移方程。
        注意到，实际操作中集合运算是十分复杂的，并且物品放入顺序显然对结果没有影响。根据自排序原则，可以规定物品按输入顺序放入，这样就把集合放到了一个数组中。
        这时，的状态就成了dp(a，p)表示从数组中1~a这个集合中拿物品，背包容量为p的最大价值。每次都按照从右向左的顺序拿，转移方程就成为

$$dp(a,p)=\begin{cases} \max\{dp(a-1，p)，dp(a-1，p-v_a)+w_a\}\ \ \ & p\geq w_a\\ dp(a-1,p) \end{cases}$$

        这就是01背包问题的DP正解。
        当然存在放入顺序影响结果的情况，见题目烹饪方案。
        这里总结两种转移方式的思考方向:

1. 先确定问题以及子问题
2. 判断是性质转移还是决策转移
3. 决策转移，根据决策列方程，注意描述清楚状态;若为性质转移，要善于发现潜在的性质，用该性质描述状态。
4. 递推或递归求解。必要时采用离散化，状态压缩，数组降维，滚动数组的方法。这些方法在本材料中都有提及。

        值得注意的是，状态设计很灵活，状态量不一定就是待求量，当前决策也可能包含在状态参量里，这些需要经验来判断。