动态规划的状态表示(一)
中国科技大学计算机系----黄浩达
一、引言
问题求解技术，包括两个方面的内容：表示和搜索。在这两个方面的内容中，搜索是重点，表示是基础。不同的状态表示对搜索的效率会产生极大的影响。一个粗糙的状态表示可能使得搜索时要对状态变换进行更多的操作，而采取简洁的表示，搜索时进行的操作可能就显得方便、高效，甚至由于状态表示准确描述了问题的本质，给人以启示，从而找到更好的搜索技术。动态规划是求解问题的一个重要技术，它的状态表示在整个算法中有着举足轻重的作用，对整个算法的影响也远比其他搜索技术中的状态表示更为深刻。
本文以实例对动态规划的状态表示进行一些讨论。
二、 动态规划对状态表示的要求
在动态规划程序设计中，我们主要利用了问题的两个性质：最优子结构和子问题重叠。最优子结构指问题的最优解包含了子问题的最优解，它是动态规划方法可行的理论基础。而一个问题具有子问题重叠性质是指用递归算法自顶向下解这个问题时，并不总是产生新的子问题，有些子问题被重复求解多次。
因为最优子结构性质，动态规划求问题最优解时，可以转化为求子问题的最优解，而对解决过的问题，动态规划则记录它的结果，当再次遇上已解决的问题，就可以直接利用结果。子问题重叠性质保证了这样做是有意义的。但一般的搜索技术，对于某个子问题不管是否已经解决过，只要遇上，就会再次对这个子问题进行求解。
很明显，动态规划与一般搜索技术最大不同的地方就是记录了已求解过的问题的结果。这里包含了两个方面的内容 ：子问题的记录和子问题结果的记录。其中，子问题的记录是最重要，也是最为复杂的，它就是通常我们所说的状态表示。
通常我们用一个数、一组数或一个向量来实现状态表示。但无论采取什么方法，从动态规划的原理来看，状态表示要满足两个要求：正确、合理描述子问题和描述的子问题满足最优子结构性质；从算法实现角度来看，状态表示必须能够用基本数据结构实现并且能满足空间要求。
下面通过两个问题来阐述动态规划对状态表示的要求。
问题一：存在一个数字三角形，从顶到底有多条路径， 每一步可沿左斜线向下或沿右斜线向下。路径所经过的数字之和称为路径得分，要求求出最小路径得分。
例： 1 1
2 3 2 3
3 2 3 3 2 3
3 8 1 2 3 8 1 2
最小路径得分=6
状态表示1-1
最自然的作法是用一元组（X）描述问题，D（X）表示从顶到达第X层的得分。但是一元组（X）描述的子问题不能满足最优子结构性质， 因为D（X）的最优解可能不包含子问题D（X-I）的最优解。这样，动态规划方法是无法在状态表示1-1上应用的。
状态表示 1-2
用二元组D（X，Y）描述问题，D（X，Y）表示到达第X层第Y个位置时的得分，那么D（X，Y）的最优解包含了子问题D（X-1，Y）或D（X-1，Y-1）的最优解，状态转移方程为
D（X，Y）= Max {D（X-1，Y），D（X-1，Y-1）} + A[X，Y]
D（1，1）= A[1,1]
这样，最小路径得分可以通过比较底层的分数求得。
一般情况下，我们找到的状态表示应能刻划子问题的特征，困难的是如何找到描述的子问题能满足最优子结构性质的状态表示，而这一点恰恰是决定该问题能否应用动态规划方法的重要因素。状态表示1-1描述的问题是正确的，但它不能满足最优子结构性质，使得无法用它来建立动态规划数学模型。状态分析的过程实际上是分析问题最优子结构的过程，不同的状态表示正是从不同的角度去试图刻划问题的最优子结构。只有状态表示描述的子问题能满足最优子结构性质，我们才能在此基础上正确的建立起动态规划数学模型。
问题二 ： 在茫茫大海中，有一座荒芜人烟的小岛，它有着肥沃的土地，终年四季如春。在许多年的沉寂后，移民者终于踏上了这块土地，接下来的事情就是对土地进行垦荒。小岛呈不规则多边形形状，为了便于管理，移民者决定将小岛划分为三角形区域且三角形区域的个数要最少，这些三角形区域的顶点必须是小岛的顶点。
显然， 用来描述小岛的多边形的任两个顶点不重合，任两条边不相交，三角形区域内只有陆地。
要求输入多边形的顶点数 n和它的顺时针坐标，返回最小区域数和具体的划分方法。
例 ： 给定如左图所示的小岛， 可有右图所示的两种划分， （1）划分为3个区域，是最优的。（2）划分为4个区域。
图（1） 图（2）
状态表示2-1
根据多边形的自然特征，一个多边形顶点的顺时针序列将正确的描述多边形的特征。例如在图（1）中，序列（1，2， …,N-1 ,N）可以表示多边形A，序列（1，2，…，K）可以表示多边形B，同样序列（K，K+1，…，N）可以表示多边形C。
由于在问题二中，多边形的顶点的序号已经隐含了顶点之间的顺序，我们只要记录多边形的顶点，而不必记录顶点顺序。基于这个性质，我们可以用一个十进制数来表示一种状态。一个十进制数通过它对应的二进制数来描述多边形。二进制数X第k位上的0、1值代表这个多边形是否包含第k个顶点。例如
（011011）2的1，2，4，5位上数值是1，则 这个二进制数代表多边形（1，2，4，5），用相应的十进制数表示就是27。
于是用一元组（A）描述多边形， D（A）表示多边形A的划分区域数。多边形B、C是由多边形划分A而成的两个多边形，那么，这种划分下，多边形的最优划分必然包含多边形B、C的最优划分，问题满足最优子结构性质。
那么状态转移方程可以表示为
D（A）= Min(D（B）+ D（C）)
子问题的空间复杂度为O(2n)，当n=20,基本堆空间就溢出了（本文假设基本堆空间是219=524288 byte并且每个子问题的状态表示只要1 byte） ，动态规划只能处理顶点数小于20的多边形。
状态表示2-2
定义2-2 多边形（A1,A2,…,Ak）是由多边形（1，2，…，N）划分而来的多边形，我们称多边形（A1,A2,…,Ak）为半连续多边形，当且仅当Ai+1 = Ai+1 ,
k>i >1。图4中多边形（1，4，5，6，7）就是一个半连续多边形。
性质2-2 对于一个多边形，它的任一顶点a只有两种划分情况：一是顶点a的两个相邻顶点连接，一是顶点a与其他顶点连接，并且这两种划分必有其一。如图3，顶点1的划分情况：顶点1的相邻顶点（2，9）连接；顶点1与顶点4连接。
我们可以用一个三元组(X,Y,Z)描述半连续多边形，D(X,Y,Z)表示半连续多边形（X，Y，Y+1，…，Z）的划分区域数。
根据性质2-1，对半连续多边形（X, Y, Z）可以只考虑顶点X 的划分，划分后的多边形仍然是半连续多边形，于是，状态表示2-2不但可以描述问题的特征，也可以正确描述子问题的特征。考虑到（X，Y，Z）最优划分包含了它的子半连续多边形的最优划分，状态表示2-2描述的子问题满足最优子结构性质。
根据定义，初始多边形是一个半连续多边形，表示为（1，2，N）。状态转移方程为
D(X,Y,Z) = Min {D(Y,Y+1,Z)+g(X,Y,Z), D(X,J,Z)+D(X,Y,J)}, Z<J<Y
f(J,I,I) = 0, n+1>I>J>0,
当X,Y,Z在一条直线时，g(X,Y,Z) = 0, 否则g(X,Y,Z) = 1。
状态表示2-2的子问题空间只有 O(n3)，动态规划最多可以处理顶点数 80的多边形。以下给出求半连续多边形最优划分区域数的函数。
[算法2-2]：
function Dynamic(x, y, z : integer) : integer;
{求半连续多边形（x,y, z）的最优划分}
var j, tot : integer;
begin
if D[x, y, z] = 255 then
if y - z = 1 then
if x,y,z三点共线 then D[x, y, z] := 0 else D[x,y,z] := 1
else
begin
if 顶点y与顶点z连接合法 then
begin
D[x,y,z] := Dynamic(y,y+1,z);
If x,y,z 三点不共线 then D[x,y,z] := D[x,y,z]+1;
End;
for j := y + 1 to z - 1 do {j 是顶点x要连接的顶点}
if 顶点x与顶点j 连接合法then
begin
Tot := Dynamic(x, y, j) + Dynamic(x, j, z);
{子多边形的最优划分}
if Tot < D[x, y, z] then
begin
D[x, y, z] := Tot;
end;
end;
end;
Dynamic := D[x, y, z];
end;
上述两种状态表示都能正确描述多边形，并且描述的多边形都能满足最优子结构性质，从动态规划原理要求来看，已经满足要求了，在状态表示2-1、状态表示2-2基础上可以正确的建立动态规划数学模型。但是，具体实现方面仍有一些问题没有解决。
从图中可以看到，状态表示2-1的空间要求随着顶点数n的增大急剧增长，正如前面所分析的，当n=20时，常用的堆空间就溢出了。而随着顶点数n的增大，状态2-2的空间要求的增大相对就缓慢多了，n一直到81堆空间才溢出。空间方面的要求强烈制约了的动态规划的处理问题能力。因此，应用动态规划时，我们采用的状态表示不仅要满足动态规划原理，还必须考虑实现状态表示的空间要求。这两方面体现了对状态表示正确性、可行性的要求，状态表示必须满足这两个要求，动态规划算法才能实现。
三、状态表示对动态规划性能的影响
我们分析问题的时候，总是从不同的角度去思考，以便能全面、本质地认识问题。分析问题的状态表示，我们也是尽可能从不同角度去思考。由此会得到对问题的不同状态表示，从动态规划原理来看，其中有些状态表示不能合乎要求，而在满足要求的那些状态表示中，我们可以以之为基础，构造动态规划模型，实现动态规划算法。在通常情况下，基于不同的状态表示的动态规划算法性能存在着差异，这主要从算法的时间复杂度和空间复杂度体现出来。
上面介绍了问题二的两种状态表示， 状态表示2-1从问题的自然特征来思考， 提出对一般多边形的表示方法，具有其通用性，状态表示2-2则根据多边形划分中关于顶点划分的性质来思考，进而提出了半连续多边形， 现在我们考虑关于多边形边的划分性质，提出状态表示2-3，
并比较三种状态表示，探讨状态表示对动态规划性能的影响。
状态表示2-3
定义2-3 多边形（A1,A2,…,Ak）是由多边形（1，2，…，N）划分而来的多边形，我们称多边形（A1,A2,…,Ak）为连续多边形，当且仅当Ai+1 = Ai+1 ,
k>i >0。图6中多边形（3，4，5，6，7）就是一个连续多边形。
性质2-3 对于一个多边形，它的任一条边一定与另一个顶点组成三角形。如图5，边（1，2）可以与顶点4等顶点相连，形成三角形。
根据性质2-3， 对多边形划分时，我们可以按需要选择边来与其他顶点相连，而不会遗漏多边形的任一种划分，自然也不会遗漏多边形的最优划分。
连续多边形（X，X+1，,…,Y）可以用二元组（X,Y）来表示，则D(X,Y)表示连续多边形的划分区域数。
对于连续多边形（X，Y），只要我们选择边（X，Y）与顶点Z(X<Z<Y)连接，那么（X，Y）划分为三部分：连续多边形（X，Z）、连续多边形（Z，Y）和三角形（X,Z,Y）。（X，Y）的最优划分包含了（X，Z）、（Z，Y）的最优划分，满足最优子结构性质。
注意到初始多边形是一个连续多边形，根据数学归纳法，它的子问题都是连续多边形。因此二元组（X，Y）是一个正确的状态表示。状态转移方程为
D(X,Y) = min(g(X,Y,Z) + D(X,Z)+D(Z,Y)), X<Z<Y,
f(i,i) = 0, n+1>i>0,
当x,y,z在一条直线时，g(x,y,z) = 0, 否则g(x,y,z) = 1。
子问题空间复杂度是O（n2），在本文的假设条件下，使用基本堆空间可以处理顶点数700以内的多边形。下面是求连续多边形最优划分区域数的函数。
[算法2-3]：
function Dynamic(s, t : integer) : integer; {求连续多边形（s,t）的最优划分}
var j, tot : integer;
begin
if D[s, t][1] = 255 then
if t - s = 1 then D[s, t][1] := 0
else
begin
for j := s + 1 to t - 1 do {j 是边（s,t）要连接的顶点}
if 顶点j与顶点s、t连接合法 then
begin
Tot := Dynamic(s, j) + Dynamic(j, t); {子多边形的最优划分}
If 顶点s、t、j不在一条直线上 then Tot := Tot + 1;
if Tot < D[s, t][1] then
begin
D[s, t][1] := Tot;
D[s, t][2] := j;
end;
end;
end;
Dynamic := D[s, t][1];
end;
图7
我们来比较三种状态表示描述的子问题空间以及相应动态规划算法的时空性能。在图7中，动态规划的时间复杂度、空间复杂度与子问题空间增长是同阶的。事实上，这样的关系不仅仅局限于这个例子，它具有普遍意义。首先，动态规划空间花费主要是用来存储描述子问题的状态表示，因此空间复杂度自然随着子问题的增多而增大。其次，动态规划的时间花费主要取决于要解决的不同子问题的数目，随着子问题数目的增多，时间复杂度当然就增大了。
既然不同的状态表示会描述不同大小的子问题空间，那么原因何在呢？在这道题中，我们仅仅从多边形的定义来看，有这样的关系：{连续多边形} 是{半连续多边形}的子集，{半连续多边形}是{多边形}的子集。由此可知，应该是状态表示描述子问题不精确造成。
回顾状态表示2-1和状态表示2-2、2-3的分析，我们之所以采取状态表示2-1 是基于对多边形自然特征的认识，而没有考虑到在特定环境下多边形划分而成的子多边形与多边形本身有特殊的联系。比较状态表示2-2、2-3，两者都利用了多边形划分的性质，但显然研究的深度不同。状态表示2-3保证了每种划分都是对多边形的不同划分，因为至少有一条边所在的三角形是与其他划分中所在的三角形不一样。状态2-2就不能保证这一点，如下图所示的两种划分顺序得出了同一种划分。因为这种无意义的划分而产生的多边形属于{半连续多边形}-{连续多边形}，如半连续多边形（1，3，5）。
状态表示的改进不仅仅使动态规划的性能提高，通常也会使算法实现更加简洁。比较算法[2-2]、[2-3]我们就可以看出这一点。算法[2-3]的程序见附录。
以上，我们主要讨论状态表示描述的子问题空间不同而影响动态规划。这是状态表示影响动态规划性能的主要原因，但是在算法实现过程中，由于某种原因我们可能对同一子问题采取了不同的描述方法，存储空间会产生极大的差异。下面这个例子说明了这个问题。
问题三： “#”这个操作符被定义为一个双目运算符，且两个运算对象为正整数，对于整数X，Y，# 号运算定义为（X#Y）=十进制数X各数字之和*十进制数Y的最大数字+十进制数Y的最小数字。例
（9#30）=9*3+0=27，（30#9）=3*9+9=36
对于表达式我们约定或是一正数或是（表达式#表达式）。以下表达式是合法的表达式
a
(a#a)
((a#a)#a)
(a#(a#a)#(a#a)#a))
对于给定的十进制正数a和表达式的值K，计算具有K值的表达式中“#”的个数。具有k值的表达式可能有许多，并且具有不同的#个数，只需输出最小个数。a，k是均不大于1000000000的正整数。
运算时，我们描述的是正整数k的各位数字和、最大数字和最小数字两个信息（这里把最大、最小数字看成一个信息）以及得到k所用的最少 # 数，那么可以有两种状态表示。
状态表示3-1
我们用一元组（k）表示正数k, D(k)表示所用的#数目。(k)已经隐含了各数字和、最大数字和最小数字两个信息。
状态表示3-2
因为对每个数而言，各位数字和与最大数字、最小数字两个信息具有独立性，我们可以分别记录这两个信息。用一元组（X）表示各位数字和，用二元组（Y,Z）表示最大数字、最小数字。
我们对输入的数a进行特殊处理，而一次运算后的最大数字不超过738，状态表示3-1只要开一个数组，定义如下
Type NumBerType = array[1..738] of integer
因为一次运算后的数值最大是三位数，各位数值和不超过27，用来存储数值和的数组可定义为
Type TotalType = array[1..27] of integer
最大数字、最小数字与数大小无关，它们范围在[0，9]，定义为
Type MaxMinType = array[0..9,0..9] of integer
状态表示3-1用一元组同时记录了两个信息，而状态表示3-2则分别记录了这两个信息。显然状态表示3-2所用的空间比状态表示3-1所用的要小的多。同样一个对象，只是由于我们采取不同的描述方法，所用的空间大小就迥然不同。程序见附录。
综上所述，状态表示对动态规划的性能的影响是多方面的。因此，在解决问题时，从各方面比较状态表示，根据具体情况选择高效的状态表示，才能进一步优化动态规划。
四、多路径问题的状态表示
动态规划是一个非常高效的算法，但是对于一些问题它并不是一个理想的算法，这里面的原因很多，最主要的原因是它的维数障碍。
下面就多路径问题来说明这点。
问题四：
存在一个数字梯形，最上层有m个数字，最底层有n个数字，每一层比上一层多一个数字，共有n-m+1层数字，如图是m=2, n=4的数字梯形。从顶到底有多条路径，每一步可沿左斜线向下或沿右斜线向下。路径所经过的数字之和称为路径得分，从顶到底的m条不相交路径的得分总和称为m条路径得分，求出最小的m路径得分。
2 3 2 3
3 4 5 3 4 5
9 1 9 1 9 1 9 1
最小的m路径得分=15
显然，这个问题与问题一极其类似。
如果m=1, 那就是问题一所要解决的问题。
如果m=2, 与问题一采取的方法类似，可以用D[x,y,z]描述两条路径到达第x层y、z两个位置的总得分。状态转移方程是
D[x,y,z] = Max{D[x-1,y,z],D[x-1,y,z-1],D[x-1,y-1,z],D[x-1,y-1,z-1]}
+A[x,y]+A[x,z],
D[1,y,z] = A[1,y]+A[1,z]
当m>=3时，可以采取类似m=2采用的状态表示。
在状态转移方程中，第x层的得分只取决与x-1层的得分，利用这个性质，实现时只要用两个循环数组，空间复杂度为O(nm)。
当m恒定时，空间复杂度随n呈多项式变化。当n恒定时，随着m的增大空间复杂度呈指数形式增长。
比如n=100 ，
当 m=2时，需要104 byte;
当 m=3时，需要106 byte;
当m=4时，需要108 byte;
我们看到当m=3时,基本的堆空间就不够存储了。在这个问题中，空间需要增长极为迅速，同时时间复杂度也是指数阶的。目前动态规划无法有效地处理这类问题，科学家把动态规划这样的缺点称为动态规划的维数障碍。它是两方面的，包括空间和时间， 但是在空间要求方面的障碍显得特别突出。
不论从空间上还是时间上考虑，动态规划的维数障碍是难以克服的，这就在很大程度上限制了动态规划的应用。所以，我们必须寻找其他的方法来解决这类问题。就这道题而言，网络流是一个高效的算法。我们可以用最小费用流来解决问题，流网络大致构造如下：
把数字梯形看成是有向图，对任意数字U看成两个顶点u1、u2,容量c(u1,u2)=1, 费用g(u1,u2)=U。若数字U沿对角线可到达数字V,则 c(u2,v1)=1, g(u2,v1)=0; 增加超级源s, 对于第一层数字U分成的顶点u1, c(s,u1)=1,
g(s,u1)=0; 增加超级汇t，对于最底层顶点U分成的顶点u2, c(u2,t)=1,g(u2,t)=0; 其他顶点之间的容量为0。
五、总结
动态规划实现并不复杂，适用于许多问题，在解决一般问题时是我们首选的算法之一。但是，动态规划的数学模型的建立不是件容易的事，其中最困难也最重要的是状态表示。通过以上分析，我们看到：
1、动态规划的状态表示描述的子问题必须满足最优子结构性质，否则无法建立正确的动态规划模型。
2、同一问题可能存在多种正确状态表示方法，它们对应的动态规划算法的性能各不相同，从中选择高效的状态表示是动态规划优化的一个重要内容。
3、对同一状态表示而言，优化它的实现方法对改进动态规划性能很有意义。
4、在应用动态规划方法解决问题时，应先估计问题的时间、空间，如果问题存在维数障碍，那么动态规划的状态表示很难满足较大规模问题的空间要求， 我们必须另寻其他方法。