topcoder算法教程翻译系列之动态规划
本文翻译自topcoder的算法教程http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/dynamic-programming-from-novice-to-advanced/
有相当一部分问题可以用动态规划（dynamic programing）来解决，下面用DP来表示。如果能够很好地掌握这类问题，那么对于编程能力将会是一个很大的提升。
本文将会教给大家如何用DP来解决问题，由于干枯的理论不便于理解，因此文章中举了很多例子来辅助对于DP的讲解。
引入
什么是动态规划？应该怎样描述它？
DP是一种算法设计技术，它是基于一个递推式和一些初始状态的。子问题的最优解是取决于子子问题的最优解的，并且子子问题的最优解是在求解子问题的最优解之前就已经算好的。
DP的时间复杂度是多项式的，这就使得它比回溯和暴力解法等算法要快得多。
接下来我们通过一个例子来看看DP的一些基本的东西。
现在有N种硬币，每种硬币的面值为（V1, V2, …, VN）。现在需要用最少的硬币凑成总和S。
接下来我们构造一个动态规划的解法。
首先，我们必须要定义一个状态，并且找到该状态的最优解，通过该状态的最优解，我们进而可以找到下一个状态的最优解。
那么什么是状态？
状态是用来描述子问题的一种方式。对于上面硬币的例子，状态i就表示对于总和i（i <= S），需要的最少硬币数。对于一个比状态i更小的状态j，它表示需要最少的硬币凑成总和j。为了找到状态i，我们需要找到所有的小于i的状态j。一旦找到了凑成总和i的最少硬币，我们就能够很容易找到下一个状态，即状态i+1。
那么怎样求得状态i？
对于每一种面值小于等于i的硬币j，我们查看凑成总和i-Vj的最少硬币数（状态i-Vj是比状态i更小的状态，之前已经求出，此时只需查表即可得到），假设凑成总和i-Vj的最少硬币数为m，如果m+1比凑成总和为i的最小硬币数的当前值要小，那么将m+1赋值给状态i。
为了更好地理解上面的表述，我们来看个例子。现在有3种硬币，每种的面值为1,3和5，总和S为11。
首先，对于状态i=0，我们认为需要的最少硬币数为0枚。紧接着，我们看S=1，由于我们没有求解过该状态的值，因此它的初始值可以设为无穷大。接下来，我们发现只有第一种硬币的面值小于等于目前的S，因此，由S-V1我们找到之前的状态0，由于状态0已经求出，我们就用状态0的最优值加上1，就得到了状态1的最优值并且保存。
接下来，我们求解状态2，同样，我们发现只有第一种硬币的面值小于等于目前的S，由于S-V1=1，问题归约为状态1，而状态1已经求出，因此状态2的最优值等于状态1的最优值加上1，也就是说，当S=2时，需要的最少硬币数为2。
同样，我们求解状态3，这次，第一种硬币的面值和第二种硬币的面值都小于等于3，因此我们得分别考察对应的情况。对于第一种硬币，问题归约为状态2（3-1），因此状态3为状态2的最优值加上1，即2+1=3；对于第二种硬币，问题归约为状态0（3-3），因此状态3为状态0的最优值加上1，即0+1=1。通过比较这两种情况，显然后者要优于前者，因此状态3等于1。
后面状态的求解以此类推。
伪码如下：
Set Min[i] equal to Infinity for all of i
Min[0]=0
For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1
Output Min[S]
下面的列表展示了所有状态的求解。
| Sum | Min. nr. of coins | Coin value added to a smaller sum to |
| 0 | 0 | - |
| 1 | 1 | 1 (0) |
| 2 | 2 | 1 (1) |
| 3 | 1 | 3 (0) |
| 4 | 2 | 1 (3) |
| 5 | 1 | 5 (0) |
| 6 | 2 | 3 (3) |
| 7 | 3 | 1 (6) |
| 8 | 2 | 3 (5) |
| 9 | 3 | 1 (8) |
| 10 | 2 | 5 (5) |
| 11 | 3 | 1 (10) |
其中第一列表示各个状态；第二列表示状态的最优值；第三列表示状态的转移，第一个数字表示凑成当前总和要加上的硬币的面值，括号内为得到当前状态的上一个状态。
最后，我们得到了凑成总和为11需要最少的硬币数为3。
另外，通过回溯，可以追踪我们是如何通过之前的状态得到当前状态的，从而可以得知最优解中用到了哪些硬币。比如说，为了得到状态11，我们把面值为1的硬币加到了状态10，为了得到状态10，我们把面值为5的硬币加到了状态5，为了得到状态5，我们把面值为5的硬币加到状态0。这样一来，我们找出了构成最终最优解的硬币为：1, 5, 5。
在了解了DP的基本使用方式后，我们来看一个稍微不同的方式，主要涉及到对于最优解的更新，不论何时发现了更好的解，都要进行更新。在这种情况下，状态的更新就不是连续进行的了。
继续考虑上面那个例子。初始时，状态0依然等于0。现在，我们把第一种硬币（面值为1）加入所有已经求得的状态，如果结果值t小于当前的状态值，那么就更新状态的值。剩下的硬币同样如上做法。
比如说，我们首先把面值为1的硬币加入状态0（因为目前只有状态0被求出），得到状态1。由于我们目前还没找到别的方式来凑成1，因此这就是目前找到的最优的状态1，S[1] = 1。接着把面值为1的硬币加入状态1，我们得到状态2，S[2] = 2。以此类推，直到得到状态11。
接着，把第二种硬币（面值为3）加入到已经求出的各个状态。把它加到状态0，我们得到状态3，此时得到了状态3等于1，这比之前的S[3] = 3更优，因此更新S[3] = 1。把它加到状态1，我们得到状态4等于2。由于之前S[4] = 4，因此更新S[4] = 2。
以此类推，每当一个更优的解被找到，就更新状态原先的值。
初阶
以上，我们介绍了一个简单的例子来说明动态规划，接下来，我们看看对于稍微难的问题，怎样找到一个方式来处理状态的转移。介于此，我们要引进一个新的术语，叫做递推关系，它在较小状态和较大状态之间建立了联系。
我们来看看其如何工作的。
给定一个含有N个元素的数组，A[1], A[2] ,…,A[N]。找出最长递增子序列的长度。
首先，我们要定义状态，它代表一个子问题。接着，我们要为这个状态找出一个最优解。需要注意的是，在大多数情况下，当前状态只和之前的较小的状态有关，和之后的较大状态无关。
我们将本例的状态定义如下：状态i表示数组前i个数中必须包含第i个数的最长递增子序列的长度。注意，对于i < j，状态i和状态j无关，也就是说在计算状态j时，状态i不会改变。接下来我们来看这些状态是怎么联系在一起的。在求出了所有比i小的状态之后，我们紧接着就可以求状态i。每个状态的初始值都为1，表示只有它自己。现在，对于每一个小于i的状态，我们逐个检查，看是否能由它转化到状态i，即能否用它构造状态i。由于我们是要构造递增的序列，因此只有A[j] <= A[i]的状态j才有可能构造出状态i。因此，如果S[j]（状态j的最优值）+1（A[i]）比状态i的当前值要更优（S[j] + 1 > S[i]），那么用它替换当前值（S[i] = S[j] + 1）。如此，我们可以找到状态N的值。
我们来看个例子：找出序列5, 3, 4, 8, 6, 7的最长递增子序列。
| I | The length of the longest | The last sequence i from |
| 1 | 1 | 1 (first number itself) |
| 2 | 1 | 2 (second number itself) |
| 3 | 2 | 2 |
| 4 | 3 | 3 |
| 5 | 3 | 3 |
| 6 | 4 | 5 |
表中左边一列表示状态，从1到6，中间一列表示状态的最优值，右边一列表示得到当前状态的上一个状态。
以下是topcoder的题目：
· ZigZag -2003 TCCC Semifinals 3
· BadNeighbors -2004 TCCC Round 4
· FlowerGarden -2004 TCCC Round 1
中阶
我们接下来看如何处理二元动态规划问题。
现有一个由N*M的格子组成的表，N代表行数，M代表每行的格子数，每个格子里面有固定数量的苹果。假设一个人从左上角的格子出发，每一步只能向下或者向右走一个格子，每到一个格子就可以得到格子里的所有苹果，如何走到右下角，才能使得获得的苹果最多。
这个问题的解答和其它DP问题的解答没有区别。
同样地，我们首先定义状态。我们首先注意到，要走到一个格子可以从两个方向来，第一个是从左边（第一列除外），第二个是从上面（第一行除外）。因此，为了找到到达该格子时的最大苹果数量，我们一定要先找到到达它左边和它上边的格子时所获得的最大苹果数量。因此，本题的状态是S[i][j]，表示到达格子(i, j)时所获得的最大苹果数量。
由以上的分析可以得到状态之间的递推关系。
S[i][j] = A[i][j] + max(S[i-1][j], S[i][j-1])，上式中i代表行，j代表列，左上角的坐标为{0, 0}。A[i][j]表示在格子(i, j)里的苹果数。注意，当格子处于第一行或是第一列的时候，上面的递推式不一定成立，因为i-1或者j-1会为负数，为了处理这种边界情况，可以先对它们进行初始化。
以下是伪码：
For i = 0 to N - 1
For j = 0 to M - 1
S[i][j] = A[i][j] +
max(S[i][j-1], if j>0 ; S[i-1][j], if i>0 ; 0)
Output S[n-1][m-1]
下面是topcoder的相关题目
· AvoidRoads -2003 TCO Semifinals 4
· ChessMetric -2003 TCCC Round 4
中高阶
这一部分将会讨论带有限制条件的DP问题。
来看一个例子。
给定一个含有N个节点的带正权的无向图G。某人有M元钱，对于每一个节点i，通过它需要支付S[i]元，如果钱不够，那么就不能通过这个节点。要求解的问题是：在钱的限制条件下，找到从节点1到节点N的最短路径，如果没有这样的路径，则说明不存在。如果存在多条最短路径，那么找出花钱最少的那条。约束条件为：1 < N <= 100；0 <= M <= 100；对于每一个节点i，0 <= S[i] <= 100。
我们能够很容易地发现，如果没有限制条件，这就是一个dijkstra问题（找出源点到某点的最短距离）。
在dijkstra问题里，我们只需要一个一维数组Min[i]来保存到点i的最短路径距离。
但在本例中，我们需要考虑钱数的限制。因此，可以将一维数组Min[i]扩展成为二维数组Min[i][j]，它的含义是到节点i的最短路径并剩下了j元钱。这里Min[i][j]就是本例的DP状态。
算法的每一步都会找一个未被处理过的状态(i, j)来求解，并且将它标记为访问过，以免后续重复访问，对于该节点i的邻居节点，算法也会检查并且更新。
重复上述过程，直到所有状态(i, j)被求出。
算法最后比较Min[N-1][j]的所有j，取最优。
以下是伪码：
Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)
Min[0][M]=0
While(TRUE)
Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).
If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.
Mark state(k,l) as visited
For All Neighbors p of Vertex k.
If (l-S[p]>=0 AND
Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For
End While
Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.
以下是一些topcoder题目：
· Jewelry -2003 TCO Online Round 4
· StripePainter -SRM 150 Div 1
· QuickSums -SRM 197 Div 2
· ShortPalindromes -SRM 165 Div 2
高阶
具体请见原文。
注意事项
当要解决一个问题的时候我们首先看看限制条件，如果要求多项式时间解决问题，那么多半要想到用DP。在这种情况下，我们需要定义状态，并且通过该状态可以求出下一个状态，在找到状态之后，接下来需要考虑如何从较小的状态转移到较大的状态，即状态之间的递推关系。如果要求解的问题看上去是个DP的问题，但是又无法找出相应的状态，那么就把要求解的问题转化成另外一个可求解的DP问题。
注：本文的部分习题代码可以参见https://github.com/ChenML/topcoder_dp