[小学]【题14】方格取数

《[小学]【题14】方格取数》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、【题14】方格取数设冇n*n的方格图（NW8）,我们将其中的某些方格中填入止整数，而其他的方格中则放入数字0。如图11.2.5所示（见样例）：向右A12345678000000000013006000000700000014000002100040000150000001400000000000000图11.2.5某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的13点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使

2、得取得的数之和最人。输入输入的第一行为一个整数N（表示N*N的方格图），接下来的每行右三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。输出只需输出一个整数，表示2条路径上取得的最大的和样例输入823132663574414522156463157214000样例输出67题解我们对这道题并不陌牛。如果求一•条数和最人的路径，读者自然会想到动态程序设计方法。现在的问题是，要找出这样的两条路径，是否也可以采用动态程序设计方法呢？回答是可以的。1.状态的设计我们衡量一个算法的标准，无

3、外乎时间、空间两项指标。“动态规划”算法的时间大多数为“多项式级”，比起同样解决这个问题的搜索算法“指数级”的时间來说，“动态规划”的时间需要是很少的，所以我们在实际应用中，很少考虑“动态规划”算法的时间问题，而最经常考虑的是空间问题：即状态的设计与存储。对于一个“动态规划”算法来说，状态的设计与存储比阶段的划分更重要，因为阶段只是一些可以等同处理的状态的集合（例如，可以将两条路径走第i步的所有可能位置定义为一个阶段）。所以，状态的选定对整个问题的处理起了决定性的作用。我们选定的状态必须满足如下两点：1：状

4、态必须完全描述出事物的性质，两个不同事物的状态是不同的；2：必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。状态是描述事物性质的量，所以我们应该以上述要求为标准，根据方格取数问题的具体情况来具体分析:我们从(1,1)出发，每走一步作为一个阶段，则可以分成2和-1个阶段：第一个阶段，两条路径从(1,1)出发；第二个阶段，两条路径可达(2,1)和(1,2)；第三个阶段，两条路径可达的位置集合为(3,1)、(2,2)和(1,3)；笫2和-1个阶段，两条路径汇聚(n,n)；在第k(l

5、WkW2*n・l)个阶段，两条路径的终端坐标(X】，yt)(X2,y2)位于对应的右下对角线上。如图11.2.6所示：如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的X坐标(X1,X2)作状态,其中(lWxiWk)A(xiG{1..n})A(lWxzWk)A(x^G{1

6、..n})直接由X坐标计算对应的Y坐标：(yi=k+l・x】)A(y)G{l..n})A(y2=k+l・X2)A(y2^{l..n})1.状态转移方程设两条路径在k阶段的状态为(xi,X2)。由(yFk+l-xJA(y.e{l..n})得出第一条路径的坐标为(Xuyi)；由(y2=k+l-x2)A(y2e{l..n})得出第二条路径的坐标为(x2,y2)o假设在k-1阶段,两条路径的状态为(x/,X2，)且(x/,X2,)位于(XI,X2)状态的左邻或下邻位置。因此我们设条路径的延伸方向为di和d2：di=

7、O,表明第i条路径由(x/,y/)向右延伸至(xi,yQ；di=l,表明第i条路径由(x/,y/)向下延伸至(心,yj(lWiW2)。显然(x/=x/)A(d.=d2),表明两条路径重合,同时取走了(x/,y/)和(xi,屮)中的数，这种取法当然不可能得到最人数和的。分析两种可能：⑴若x产X2,则两条路径会合于XI状态,可取走(Xi,y.)中的数(图11.2.6)；X1Z(X2‘)fX1=X2tX/(x/)图11.2.6⑵若X】HX2,则在k阶段，第一条路径由X/状态延伸至Xi状态，第二条路径由X2,状态延

8、伸至X2状态,两条路径可分别取走(XI,V!)和(X2,y2)中的数(图11.2.7)；图11.2.7设f[k,XuX2]—在笫k阶段，两条路径分别行至Xi状态和X2状态的最大数和。显然k=1时，f[1,1,1]=0；kM2时，f[k,Xi,x2]=max｛f[k-1,x/,x2z]+(xi,yj的数字Ixfx2f[k-1,x/,x2z]+(xi,yj的数字+(X2,y2)的数字IxiHx2｝1WkW2*nT,x