《算法竞赛入门经典（第二版）》第九章。
动态规划是个很“大”的设计思想，此处姑且记录一些【原型】等。

(省略作为引入的数字三角形和记忆化递归搜索)

总说#

动态规划有两个关键，一个是对状态的描述与设计，一个是状态转移公式。只要整出了这两个，最不济用记忆化递归也可以比较方便地写出来。（递推一般是比较难写的）。

常见的状态设计经验可能是

• 从某个点/状态开始 / 结束的点。
• 考虑了 1~i 情况下的解。
• 第几步 / 阶段，将要做什么而目标怎么样时的解。
• 搜索子集时，直接以二进制表示子集为状态。
• 天然序列，并且和解有密切关系，比如时间等。
• 需要求最小、最大解，状态中往往使用”在此状态时至少、最多还需要多少“，解释为“余量”。
  有时候从最小规模问题（这样一般是显然）开始考虑可能会对状态设计有帮助。 可以多种结合为多维状态。

关于状态转移方程
一定记得有时候不需要追求“一步到位”的优美的状态转移，适当的暴力是可以接受的。

最少回文子串
给一个字符串，将它划分为多个子串，使每个子串都是回文串。求解最少回文子串数量。
解：
令 d[i] 是已经考虑了第 1i 个字符的最小回文子串数量。知 d[i]==1。状态转移方程为
d [ i+1 ] = min { d [ j ]+1 | j~i+1是回文串 }
尾巴回文串也挺暴力的。
也可以提前预处理出 H[ i ][ j ] 表示 ij 是否是回文串，方法是枚举中间那个字符，然后往两边扩散直到不相等。

有向无环图的动态规划#

有向无环图可以归入图论，也可以放在动态规划，这里的动态规划还不是那么“典型”。

没有起点终点的最长路径#

最长路径问题我之前想到一个基于拓扑排序的方法，实际上动态规划的思想和用图论的想法去解是等价的，一个是动态规划的“填表法”，一个是“刷表法”。

填表法：  
完全基于状态转移方程求解。递推或者记忆化递归搜索。  
刷表法：  
每次计算完一个状态的结果后，“更新”收到这个状态影响的所有状态的“当前最优解”。  
（以已经计算完的状态为状态转移方程等式右边，被刷新的为左边那个）。  

以动态规划去描述（填表）
令 d[ i ] 为以结点 i 为起点的最长路径。基础为：出度为零的结点最长路径为0.
状态转移方程为：
d[ i ] = max { d[ j ] + w(i, j) | (i, j)属于边集E } 即 j 是从 i 出发的所有下一个可能的点，w是边的权重，常常是1，也有可能有其它值。都可以使用。
用记忆化递归实现。

基于拓扑排序的描述（刷表）
从出度为0的点开始，最开始的点从它出发的最长路径是0. 每弹出一个出度为0的点，更新它的“上一级”结点（能通往它的结点），如果能让路径变长，就更新。然后删除这个刚弹出的结点，其“上一级”结点全部出度-1，然后接着弹出任意新的出度为0的点，重复上述过程。如果点没有弹完但没有了出度为0的点，说明有环。
从动态规划的角度理解，这就是刷表。每次确定某个状态的解时（弹出出度为0），更新受它影响的状态。

解的输出
所有 d[i] 中最大的为所需最长路径的起点，然后查找它能到达的下一个结点 j ，必使得 d[ j ] = d[ i ] - w(i, j)，可以挑选字典序等约束. 和之前倒过来BFS求最短路的字典序最小路径方法一样。

注意没有起点、终点的最短路径是无意义的。

确定终点的最短 / 最长路径#

动态规划中，这一类问题往往是隐式图，题目中的某些约束为形成状态，某些操作形成状态转移——即边。我觉得这其实更像装载或背包问题。不在此处详述。
这里简单说下显式图的确定终点最短 / 最长路径。可以将有向图倒转，即所有边转个方向，(i, j) -> (j, i)，然后变成确定起点的最短 / 最长路径，用 Dijkstra 即可。

题目欣赏#

题目可能看上去和上面的内容没多大关系…

巧妙状态设计#

城市间谍
1~n个站，站点之间距离相等，双向不断有列车通行（走完1~n or n~1），同一个方向有相同的发车间隔与行驶完两个相邻站的时间。间谍时刻0从1出发，要在时刻T准时到达n与接应人员汇合，由于在站台上等待容易被抓，所以间谍需要尽可能减少在站台上的等待时间。输出最优解，或者可能无解（怎么样也无法准时到达）。

时间是天然的状态序列。令 d[t][i] 表示 t 时刻间谍在 i 站台，最少 还 需要等待多长时间。
状态转移：
1）如果不坐车，则 d[t][i] = d[t+1][i] + 1。（下一个时刻一定还在这个站台）。
2）如果有向左的车，则 d[t][i] = d[t+向左到下一站的时间][i-1]。这个时刻不等，t+向左到达下一站的时间回到 i-1 站，这形成了状态转移。
3）如果有向右的车，则 d[t][i] = d[t+向右到下一站的时间][i+1]。和2很像。
从三者中选择最小的。
基础 d[T][n]=0, d[T][!=n]=INF。答案 d[0][1].
需要提前维护 train[t][i][s] 表示 t 时刻在 i 站台是否有 s（0,1-人为规定） 方向的车。

巧妙表示状态#

巴比伦塔
有n（n<=30）种长方体，每种都有无限多个，要求选一些长方体摞成尽量高的塔，其中，只有一个长方体的底面长、宽均小于最顶层的长方体时，这个长方体才能被放在最上面。长方体可以旋转。

用边权表示高
底面的“嵌套”可以视为明显的二元关系，组成有向无环图，因为尽可能高，长方体的高为边长。比如长方体a可以放到长方体b, c之上，则a有通向b, c的边，并且边权为长方体a的高，表示把a放在b, c之上能增高多少。
长方体可以旋转，规定作为底面的边一定长大于宽，这样每种长方体实际对应了三种“子长方体”，然后对这 3n 种不可旋转的长方体建图即可。 可以直接暴力地给3n个“子长方体”编新的编号，也可以 间接表示状态 。用 (idx, k) 表示原本第 idx 种长方体，以输入中第 k 边为高。

多阶段决策与背包#

说到动态规划，往往一下子想到的，就是多阶段决策（比如那个数字三角形）。阶段，可以理解为步骤，在前面都走完的情况下，下一步要怎么走。
多阶段决策动态规划和回溯 枚举有千丝万缕的联系。动态规划也要遍历当前所有可能的选择（体现在状态中），不过动态规划问题能从前面已有的解答数（层数）直接递推出新一步的最优解（往往也伴随着一定程度的暴力与枚举），从而避免了回溯法必须心里没底地试探。

经典0-1背包#

0-1，即选或者不选。
有 n 种物品，每种体积 Vi，每种价值 Wi，背包容积C，需要尽可能装得价值最高。

令 d[i][c] 表示在决定 i 是否要选择（即1i-1已经选择完毕的情况下,一定注意把握，这类问题状态隐含前几个已经决策完毕！正要决定这个！）并且剩余容积为 c 时，还能装的最大价值。显然 d[n][<Vn]=0, d[n][>=Vn] = Wn。
状态转移：
1）如果剩余容积小于 Vi，i无论如何选不了。d[i][c] = d[i+1][c]——确定 i 不选，1i 确定，要选 i+1.
2）如果容积大于Vi，可以选i。d[i][c] = max(d[i+1][c], d[i+1][c-Vi])——从选或不选中选择大的。从这里可以看出 回溯暴力 的痕迹。
答案是 d[1][C]。

int solution(int n, int *V, int *W, int C) // V W 从 1 开始  
{  
	int dp[n+1][C+1]={0}, i, j;  
	for(i=0;i<=C;i++){  
		if(i>=V[n])  
			dp[n][i]=W[n];  
	}  
	for(i=n-1;i>=1;i--){  //要决策第 i 个选还是不选。  
		for(j=0;j<=C;j++){  //遍历所有剩余容量。  
			if(j<V[i])        //容量不足以选这个，必定不选.  
				dp[i][j] = dp[i+1][j];  
			else  
				dp[i][j] = max(dp[i+1][j], dp[i+1][j-V[i]]+W[i]);  
		}  
	}  
	return dp[1][C];  
}  

note
这里 C 的处理涉及到离散化的处理。动态规划中，有时候一些量不好处理，如果有范围的话可以直接放进状态中，遍历。

滚动窗口
当状态转移方程是不断向前，即只会随着下标增大越来越往后取，比如上面那个第二维剩余容积，当前 i 确定，随着 j 增大只可能选越来越大的，小的用过一次就不用了，可以放心覆盖，则可以改成滚动窗口，用一维数组完成这个任务。具体就是直接把上面程序里二维数组的第一维删了，其它不用改。

微弱改版#

n个物体，体积Vi，背包总体积 C，尽可能多装，能装多少。
这个问题曾击沉过我——实际上就是使价值等于体积的0-1背包！其它完全相同！！
具体化的描述是：d[i][c], 要选择是否装第 i 个物体，而剩下容积c,最多还能装多少体积的物体。

不限量版#

上述物体要么选要么不选，每个物体只有一个。如果物体不限量？最多装多少价值？
这里不是多阶段决策，书中归入上面的有向无环图，不同的剩余容积为结点，建模成了 一个隐式图。
d[c] 表示已经装了体积 c ，能装的最大价值。d[0~min(Vi)]=0, d[min(V1)]=Wi.
d[c] = max(d[c-Vi]+Wi)。答案为所有d中最大的。

凑硬币
有n种面值的硬币，不限量，要凑出面值W，问要使用的最多、最少硬币数量。

所有价值为1，其它和上面一样。记得凑不出来应该用（最多硬币用-INF，最少硬币用+INF）。d[W]为答案，可能无解。

线性结构动态规划#

非常常见已经确定只有前 i 个时的该问题的解，或者以某一个为始/终的解来设计状态。难点在于状态转移。。状态转移可以适当暴力！

最长递增子序列
从序列中截取最长递增子序列，注意不必连续。

d[i]为以 i 结尾的最长递增子序列。
d[i] = max{d[j]+1 | j<i && A[ j ] < A[ i ] }
答案为所有 d 中最大的。

最长公共子序列

d[i][j] 为考虑了第一个序列前 i 个、第二个序列前 j 个的解。
如果 A[ i ] = B[j], d[i][j] = d[i-1][j-1] + 1.
否则 d[i][j] = max{ d[ i-1 ][ j ], d[ i ][ j-1 ] }. 因为不可能同时选择新加入的那一个！！

电灯设计
有多种等，每种灯有若干个（给出），每种灯有不同的额定电压，给出种数相同的和所有额定电压相等的电源，每个电源价格一样。假设流过每种灯的电流相等，所以电压越大越贵。但是低电压等可以用高电压电源节省电源费用。给出 1 ~ n 种灯泡的电压和数量。求最便宜方案。

可知每种灯要么不换，要么全换。只换部分省不了电源费用，还会让换了的灯泡费用增加。
将灯泡按电压升序排列。令 d[ i ] 是灯泡 1i 的最优策略，则转移为：
d[ i ] = min { d[ j ] + (j+1~i 灯全部用最高电压(i)灯电源的费用 ) }
意义为让前 j 灯用最优策略，然后 j+1i 全部用电压最高的 i 灯的电源。这样能成立，应该还蕴含了一个贪心的思想，要用更高电压的电源，也应该尽可能不要高太多。

遍历分治+记忆化递归#

可以改写成动态规划形式，经典如最优矩阵链乘。
这个记忆比较深刻。
最优三角剖分也很相似。

最优三角剖分
将凸 n 边形划分为 n-2 个（最多）不重叠的三角形，给每个三角形定义一个权重，比如周长或者其它定义，求解一个最小（大）权重的划分。

多边形每个边都会出现在某个三角形内。
将顶点逆时针（或者顺时针）编号 V1…Vn，边 V1Vn 一定在某个三角形中。
选定 V1Vn，遍历第三个顶点(V2…Vn-1)，然后这个三角形两边的多边形分别取最优剖分（步骤一样），加上遍历的那个三角形，从所有中求最优，这就是个遍历分治算法。
best(V1…Vn) = min { tri(V1, Vn, Vk) + best(V1…Vk-1) + best(Vk+1…Vn) }
可以用和矩阵链乘几乎一样的方法转化为递推。

树上动态规划#

树的分层结构和严格的子节点、父节点、子树的概念是天然的拆分子问题 的暗示，树上很多问题和递归、递推动态规划有关。同样，在以子问题为导向思考时，把子节点当“子树的根”会有帮助。并且由于树天然适合递归，按子树递归遍历不会有重复，递归连记忆化都不需要。

一个注意：很多题不会给标准的树，而是一个无根树(满足树的要求，无向，联通，无环，n-1条边)，这样的情况任选一个结点为根，与其相邻的结点都是儿子，一层一层下去，就成了有根树。

最大独立集
给出一个n节点无根树，求一个元素最多的节点子集，使得集合中所有节点两两不相邻。

任选一个节点为根，这样就有了标准的儿子等结构。
以 i 为根的子树，如果集合中选 i ，则这颗子树的最大独立集是所有孙子子树的最大独立集之和+1；如果不选 i，则这子树是所有儿子子树的最大独立集之和。两者取数量最大。

int solution(Tree *root)  
{  
	if(root is leaf)  
		return 1;  
	int choose_root = 1, no_root = 0;  
	/* 选择root */  
	for(each grandson node of root)  
		if(grandson != NULL)  
			choose_root += solution(grandson);  
	for(each son node of root)  
		no_root += solution(son);  
	return max(choose_root, no_root);  
}  

树的重心
给一颗n节点无根树，找到一个根，使此根的所有子树中的最大节点数最小。

随便找一个根 r ，用一个DFS遍历得到 d[ i ] 表示以 i 为根的子树的节点数。则任意以任意节点为根，最多节点子树的节点数为
d[ i ] = max{ d[以 r 为根时 i 的儿子], n-d[ i ] }
以 r 为根时， i 的子树仍是以 i 为根时的子树，而 n-d[ i ] 为 r 为根时 i 上面 的子树的节点数。

树上最长路径
给一颗无根树，求无重复边最长路径

这题动态规划其实比较麻烦。经过 i 第最长路径，就是以 i 为根的所有子树中最大的两个深度之和 + 2。遍历所有节点，求以这个节点未根的所有儿子树的最大深度，如果只有一颗子树就+1，如果有多个就两个最大深度之和+2. 复杂度似乎是 O(n^2^)。
以不同节点为根的所有儿子子树的最大深度这一步可以动态规划，任选一个根，在此根下求所有节点子树的最大深度，然后遍历的时候，每次都从根进入子节点，新的儿子子树最大深度可以从父状态直接求解。

可以不用动态规划，单纯从图的角度说。任选节点为根，DFS一下得最远点v，从v开始DFS求最远点w，v-w就是最长路径。
正确性：第一次DFS一定能找到最长路径的两个断点之一：1）如果所选根在最长路径之中，显然能找到一个节点。2）如果不在，由树的性质，一定存在唯一 路径到最长路径上的某个节点，这加强了这个节点到所需端点的距离。不便表述，但一定是更长了。

强化：n节点无根树每个节点的最远点

这个还好。结点 i 的最远点一定是以 i 为根时候的最大深度。可以动态规划。用进入子树时候的”旋转“。

复杂状态动态规划#

和集合有关的动态规划，其实几乎是对暴力枚举的优化。
这个比较复杂，回到了巧妙的状态设计与状态转移等，难以寻迹。

最小点对
n个点 P1…Pn，偶数个，两两配对，使点对组成的线段的长度和最小。

状态设计：前 i 个 + 二进制子集。
d[ i ][ s ] 为考虑前 i 个点，s是待确定的前 i 个点的子集时的最优解。 d[ i ][ s ]=min{ d[ i-1 ][ s-{j}-{i} ] + |PiPj| | j属于s }
可见是遍历了j, 尝试让 i 与 j 配对。
结果在 d[n][2^n^-1]，记忆化递归。

担货郎
n个城市两两有道路，给出距离。求解一个最短路径长度，使担货郎经过每个城市恰好一次后回到起点（0）。（不约束边）

这是一个经典的NPC问题，问题规模较小可以用动态规划。这个动态规划又有浓浓的枚举意味。
状态 d[i][S]，人在城市 i ，还有集合S中的城市要走，最小还要走多远？
d[ i ][ S ] = min { d[ j ][ S-{ j } ] + dist(i, j) | j 属于S }
记忆化递归，初始是 d[0][2^n^-1], 终止条件是 d[k][0]=dist(0, k).