动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。[例9]街道问题在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：(这里的row是地图竖直方向的行数）我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：（这里Distance表示相邻两点间的边长）这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的"状态转移"就不全是在两个阶段之间进行的了。也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种"简单"的方法就不太好办了。如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径"不能重叠"的问题。而我们回到原先"标准"的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用xk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：从这个例子可以看出，合理地划分阶段和选择状态可以给解题带来方便。[例10]LITTLESHOPOFFLOWERS（IOI’99）PROBLEMYouwanttoarrangethewindowofyourflowershopinamostpleasantway.YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastasmanyvasesorderedinarow.Thevasesaregluedontotheshelfandarenumberedconsecutively1throughV,whereVisthenumberofvases,fromlefttorightsothatthevase1istheleftmost,andthevaseVistherightmostvase.Thebunchesaremoveableandareuniquelyidentifiedbyintegersbetween1andF.Theseid-numbershaveasignificance:Theydeterminetherequiredorderofappearanceoftheflowerbunchesintherowofvasessothatthebunchimustbeinavasetotheleftofthevasecontainingbunchjwheneveri
