Algorithms第六章动态规划
这一章以DAG中的最短路开头。对于DAG，所有的节点都是可以linearized的，也就是说所有的点可以排在一排，然后所有的点都只从左到右，没有从右到左的边。
上图中，如果要算S到D的距离，那么必须从D的前驱{B,C}中任选一个最为D的前一个节点，那么我们只需要算dist(D) = min{dist(B)+1, dist(C)+3}，同理，我们可以得到所有的节点的dist。我们可以一次性算出所有点的dist，步骤如下：
dist(s) = 0
for each v ∈ V\{s}, in linearized order:
dist(v) = min{dist(u)+l(u,v)} ((u,v)∈E)
注意到，这个问题是通过解决一系列的子问题{dist(u) : u∈V}来解决的。我们先解决了最小的dist(s)问题，然后通过DAG的linearized性质解决更大的问题。最终解决所有的问题。
动态规划问题就是一种通过子问题来不断解决问题的有效算法。在动态规划问题中，不会明确的给出我们一个DAG图，这个DAG图是隐藏在题目中的。这个DAG的所有节点都是我们定义的子问题，边则是子问题的依赖性：加入我们解决子问题B之前必须解决子问题A的话，那么就会有一条从A到B的边。
接下来讲的是最长上升子序列的问题：给你一串数字，然后需要你求出这串数字中一个严格递增的子序列，且这个子序列最长。比如说序列：5,2,8,6,3,6,9,7的最长上升子序列是2,3,6,9.长度为4.这个序列的最长上升子序列的DAG如下图所示：
上图中的箭头表示可以从左边的数字到右边的数字，即在他们可以在同一个上升子序列中。我们注意到(1)上图是一个DAG，而且所有的边(i,j)都有i<j;(2)上图中的每一条路径对应原序列中的一个上升子序列。这样我们只需要找出上图中最长的路径就可以了。算法如下：
L(j) = 1 + max{L(i):(i,j)∈E}
return max{L(j)}
其中L(j)表示已j为结尾点的最长上升子序列的长度，因为所有以j为结尾点的路径都会经过j的前驱节点，所以L(j) = 1 + max{L(i):(i,j)∈E}.我们需要的是全局最大值，而任意点为结尾都是可以的，所以最后我们返回max{L(j)}。这就是动态规划的主要思想：为了解决我们的原问题，我们定义了一系列的子问题{L(j): 1 <= j <= n}，而且解决某个子问题之前，它所需要的其他更小的子问题都已经被解决。这个问题中，我们的子问题就是L(j) = 1 + max{L(i): (i,j)∈E}.
接下来出场的是叫做编辑距离的问题。这个问题也算比较经典了，很多地方都可以看到。大致意思就是给你两个字符串，可以在字符串中间插入任意的空格，然后对比两个字符串中不同字符的个数。比如
其中-表示的是空格。下面的cost表示的是不同字符的个数[这里一个不同字符的cost为1，而且所有的字符cost都一样]，在解决动态规划问题我们主要的问题就是要找到子问题，且子问题满足上面标红的动态规划主要思想。我们的目标是找到x[1 … m] 和y[1 … n]两个字符串之间的编辑距离。那么什么是一个好的子问题呢？如果我们去x的前i个字符和y的前j个字符，然后把这个算作一个子问题E(i,j)的话，那么我们的目标就是要算E(m,n)。这样的话，我们需要把E(i,j)用更小的子问题来描述，我们考虑最右一个字符的匹配情况，只有下面三种情况：
第一种情况会使cost增加1，然后变成了子问题E(i-1,j)，也就是x[1 … i-1]和y[1 … j]；第二种情况会变成子问题E(i, j-1)cost会增加1，第三种情况则会变成子问题E(i-1,j-1),cost的值则根据x[i] 和 y[j]是否相等来判断，如果x[i]==y[j]则cost为0，否则cost为1。这样的话E(i,j) = min{1+E(i-1,j),1+E(i,j-1), diff(i,j)+E(i-1,j-1)}这里的diff(i,j)表示的是x[i]是否等于y[j]，相等则返回0，否则返回1.比如我们算EXPONENTIAL和POLYNOMIAL两个字符串的子问题E(4,3)的时候，也就是前缀EXPO和POL，他们最右边的匹配一定是下面中的一种：
也就是说E(4,3) = min{1+E(3,3), 1 + E(4,2), 1 + E(3,2)}，所有的E(i,j)讲得到一张表格，如下图所示：
那么应该以一个什么样的顺序来解决子问题呢，在这个问题中，不过什么样的顺序都是可以的，因为在算E(i,j)的时候，E(i-1,j)，E(i,j-1)和E(i-1,j-1)都已经被算出来了。我们可以每次填一行，从上到下，每一行从左到右；也可以每次填一列，从左到右，每一列从上到下。这样的顺序下，我们所需要的子问题都已经在之前就被解决了。现在只剩下”base cases”了，也就是初始化的问题，也可以说是最小的子问题了，这里就是E(0, )和E( , 0)这个好解决，对所有的E(0, i)都等于i，对所有的E(j,0)都等于j。因为空字符串和长为i的的字符串的编辑距离就是i。这样的话，这个问题的算法如下：
E(i, 0) = i
for j = 0, 1, 2, …, n:
E(0, j) = j
for i = 1, 2, …, m:
for j = 1, 2, …, n:
E(i,j) = min{E(i-1,j)+1, E(i, j-1)+1, E(i-1,j-1)+diff(i,j)}
return E(m,n)
上述算法是每次填一行，然后从左到右的顺序。对于每一个动态规划问题都有一个隐藏的DAG，编辑距离的DAG如图所示[EXPONENTIAL和POLYNOMIAL]
我们可以更改DAG的边权值来适应不同的要求。比如编辑距离的增删cost。这个问题和DNA问题也是很类似的，比如给你两条DNA，然后给出一些条件，然后问两条DNA的差距有多大。
接下来讲了背包问题的两中变种。背包问题是指：有一个容量为W的背包，然后有n种物品，每一种物品的价值和体积分别为w1,…,wn和v1, …, vn.问怎么添加物品，使得背包中物品的总价值最大。比如W=10，然后有以下4个物品：
背包问题有多个变种，这里讲的两种是：1）每个物品都是有限数目的，2）每个物品的可选数目是无限的。如果每个物品的可选数目都是无限的话，那么最优Item 1和Item 4(total: $48). 如果每一种物品都只有一件的话，那么最优的则是选择Item 1和Item 3(total: $46)。我们先来看物品有无限多的这一种情况。在动态规划问题中，最重要的是子问题的选取，这个问题中，子问题的选取，我们有两种可能，1是我们以背包容量作为子问题(w<=W)，或者我们以物品的种类为子问题for instance, items 1, 2, …, j, for j <=n).要找出哪个子问题可行或者哪个子问题更好需要一定的经验。
如果我们把容量作为子问题的话，我们设K(w) = maximum value achievable with a knapsack of capacity w.那么我们只需要知道怎么用更小的子问题来表示当前问题，也就是传说中的状态转移。如果K(w)的最优值中包含了Item i，那么K(w)可以转到K(w-wi)，且K(w-wi)也肯定是最优的，也就是K(w) = K(w-wi)+vi.但是我们不知道这个i是哪个，所以需要测试所有的可能性。也就是K(w) = max{K(w-wi)+vi} (i:wi<=w)，对于空背包最优价值就变成了0，这样的话我们就得到了如下算法：
for w = 1 to W:
K(w) = max{K(w-wi)+vi : wi <= w}
return K(W)
这个算法的时间复杂度为W每个K(w)的时间，而每个K(w)的时间都是n，所以总时间是nW。对于这个算法也可以画出一个DAG出来，其中节点表示容量，然后边表示价值，那么我们要找的就是一个最长路径。
下面的则是各种物品都只有一件的情况，那么上面的子问题就不行了，因为你不能确定到底Item是否已被选，我们得重新定义我们的子问题，我们需要加上一维表示当前想选的Item是否可用。我们可以用K(w,j)表示maximum value achievable using a knapsack of capacity w and items 1, …, j那么我们最后的答案就是K(W,n)，现在需要想怎么用更小的子问题来描述当前子问题，我们只要考虑两种情况就行了，K(w,j)的最优情况中Item j是否被选中就行了，也就是K(w,j) = max{K(w-wj, j-1)+vj, K(w,j-1)}前面一种情况表示Item j被选中，后面一种情况表示Item j没有被选中。那么算法就出来了：
for j = 1 to n:
for w = 1 to W:
if wj>w: K(w,j) = K(w,j-1)
else: K(w,j) = max{K(w,j-1),K(w-wj,j-1)+vj}
return K(W,n)
这个算法的总时间复杂度也是O(nW)的，就是两重循环的时间。至于内存的问题，有关背包的这两个问题都可以利用滚动数组来实现低内存的使用。
接下来是矩阵乘的问题，给一个含有n个矩阵的矩阵乘式子，让你给出合适的矩阵乘顺序，使得总得乘积次数最少。这个的子问题可以看成是C(i,j)表示minimum cost of multiplying Ai A(i+1) … Aj，那么最小的子问题就是当i==j的时候，也就是C(i,i)。那么我们只需要看怎么表示C(i,j)。也就是C(i,j)=min{C(i,k) + C(k+1,j) + m(i-1)m(k)*m(j)} {i<=k < j}也就是在[i,j]之间找一个点，然后把这个序列分开，先乘起来之后，然后再把两部分乘起来。算法如下：
for s = 1 to n-1 :
for i = 1 to n-s;:
j = i+s
C(i,j) = min{C(i,k)+C(k+1,j)+m(i-1)m(k)m(j): i <= k <= j}
return C(1,n)
这个算法的复杂度是O(n^3)。外层两个循环，然后算C(i,j)的时候是O(n)的。所以总复杂度是O(n^3)。
接下来是最短路的变种，以及所有点之间的最短路问题。
我们一般的最短路是求从源点s到其他点的最短路就行了，没有什么限制，不过如果我们加一个限制：最短路径上的边的条数不能超过k条。这样的话Dijkstra就不能直接用了，而且不太好改，因为Dijkstra算法中没有记录每条路径上有多少条边。在动态规划问题中，我们需要确定合适的子问题来记录足够的信息提供给后面的问题。在这个问题中，我们定义dist(v,i)：从源点s到v且使用了i条边的最短路径，初始化的时候，dist(v,0) = ∞，dist(s,0) = 0.那么转移方程变成：dist(v,i) = min { dist(u,i-1) + l(u,v)} {(u,v) ∈E}.接下来如果我们想算所有点之间的距离，而不是单源最短路径。我们可以运行V次单源最短路算法，因为边可能是负的，所以不能用Dijkstra算法，这样总时间复杂度为O(V^2E)，我们可以看到一个复杂度为O(V^3)的动态规划算法。我们需要找到合适的子问题，我们知道从u到v可能经过一系列顶点。我们可以用dist(i,j,k)来表示子问题，dist(i,j,k)的意思则表示：从i到j则只能用前k个顶点的最短路径。dist(i,j,0)初始化为i到j的直接距离，如果i到j没有边的话就置为∞。对于每一对顶点的距离，我们考虑把是否经过顶点k，来更新顶点i到顶点j之间的距离，也就是说看dist(i,k,k-1)+dist(k,j,k-1)是否dist(i,j,k-1).接下来算法就简单了
for j=1 to n:
dist(i,j,0) = ∞
for all (i,j) ∈ E:
dist(i,j,0) = l(i,j)
for k = 1 to n:
for i = 1 to n:
for j = 1 to n:
dist(i,j,k) = min{dist(i,k,k-1)+dist(k,j,k-1),dist(i,j,k-1)}
这个算法的总时间复杂度是O(V^3)。可以算出任意两点之间的最短距离，而且这个可以更改参数来适应不同的场景和要求。
接下来是旅行商问题和树上的最大独立集问题。这两个就直接给出一个大概思路和算法了。
旅行商问题中，我们让C(S,j)表示访问S中的每个顶点一次，且从1开始，到j结束的最短路径，如果|S|>1的话，那么我们使得C(S,1)=∞，因为路径不能从1开始，在1结束。转移方程为C(S,j) = min {C(S-{j},i)+d(ij)} {i∈S: i =/= j).算法如下：
for s = 2 to n:
for all subsets S ∈ {1, 2, …, n} of size s and containing 1:
C(S, 1) = ∞
for all j ∈S, j=/=1:
C(S,j) = min{C(S-{j}, i) + d(ij) : i ∈S , i =/= j}
return min{C({1, …, n}, j) + dj1}
总时间复杂度为O(n^2*2^n)。
树上的最大独立集问题，可以做到线性时间，那么子问题怎么确定呢？我们可以用I(u)表示已u为根节点的子树的最大独立集的数目，那么转移方程可以写成I(u) = max{1 + ∑I(v), ∑I(w)}(其中v是u的孙子节点，w是u的儿子节点)。也就是说算u点出的最大独立集的时候，可以考虑是否把顶点u算进去，如果算进去的话，那么儿子节点都不能算进去，也就变成了1+∑I(v)其中v是u的孙子节点，如果u不算进去的话，那么就是后面那一个表达式∑I(w)。这个算法的总时间复杂度是O(V+E)的。
这一章讲的动态规划问题算是比较灵活的了，这东西还是要多练习，需要选取合适的子问题，然后写出转移方程。至于动态规划的优化问题，那就属于更深层次的问题了。对于相应的问题可以google查找资料，由于ACM比赛的存在，这一块的资料还是很多的。
