(牛X)动态规入门篇.ppt.pptVIP

状态表示法三： 采用状态表示法二的方法是从顶层开始，逐步向下至底层来求出原问题的解。事实上，还可以从相反的方向考虑。仍用二元组D(X,y)描述问题，D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为D(1,1)。 最优子结构性质：显然，D(X,y)的最优路径Path(X,y)一定包含子问题D(X+1,y)或D(X+1,y+1)的最优路径，否则，取D(X+1,y)和D(X+1,y+1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分，这与Path(X,y)的最优性矛盾。 2 6 2 1 8 4 1 5 6 8 图1—1 数字三角形 如图所示，D(1，1)的最优路径为2-6-1-1，它包含D(2,1)的最优路径6-1-1。因此，这种状态表示描述的计算D(X，y)的问题同样具有最优子结构性质。 递归关系： D(X,y)＝min{D(X+1,y),D(X+1,y+1)}+a(X,y) D(N,k)＝a(N,k)，k＝1，…，N 其中，a(X，y)为第X层第y个位置的数值。 D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为D(1,1)。 算法设计 采用状态表示法三的算法的主要过程如下： for ( i = n - 2; i = 0; --i ) //从最下层开始，计算每个x，y位 //置的元素到 最后一行的最小值 { for ( j = 0; j = i; ++j ) //计算每一行的每一个数字 { tmp = sou[i + 1][j]; if ( sou[i + 1][j + 1] tmp ) /*j在变化，j每循环完次都得到一个这一行到最底行最小的位置，同时也记录了每个位置到最底行的值；这里的if是在找每个位置的下两步路线中较小的一个*/ { tmp = sou[i + 1][j + 1]; } sou[i][j] += tmp; } } printf( %d\n, sou[0][0] ); 例题二：花束摆放 问题描述 现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(F≤V)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。 2009-8-12 成都大学ACM暑期集训DP篇——李明金 * 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。 2．解题思路 状态表示法一： 设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(这里k≥i)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可以通过计算max{S(F,k)?F≤k≤V}获得。 下面要分析一下这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。 最优子结构性质：对满足F≤k≤V的k，设T(F,k)是达到最优值S(F,k)的一种最佳摆放方式，其中，第F-1种花束摆在第j个花瓶中(jk)，则T(F,k)中前F-1种花束的摆放方式获得的美学值为S(F-1,j)。故对每个满足F≤k≤V的k，计算S(F,k)的问题具有最优子结构性质。 递归方程： S(i,k)=max{S(i-1,j)?i-1≤j≤k-1} + A(i,k), i1 每走一步，计算出了所有i的花束摆放在所有可能的位置之后的所有值。最后，递推出了s(F,*)的值取最大既得到结果。 S(1,k)=A(1,k) 第i-1个花摆在那里之后，下一步怎么摆，只跟现在花在哪里有关，而与前面的摆放顺序无关，无后效性。 大家用心想一下，问题其实还是像装配线一样，被分解成了有限个分支的最大值问题。 切记，使用DP的时候，眼光不要一直盯着最后的最优，一步一步看，只要你现在最优，并且无后效性，就可以DP下去。 在计算S(i,k-1)时，已经计算出了S(i-1,j)，i-1