【题14】方格取数.doc

【题14】方格取数 设有n*n的方格图（Ｎ≤８），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字０。如图１１.2.5所示（见样例）： 向右 　 A 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 2 0 0 13 0 0 6 0 0 3 0 0 0 0 7 0 0 0 4 0 0 0 14 0 0 0 0 5 0 21 0 0 0 4 0 0 　　　向 6 0 0 15 0 0 0 0 0 　　　下 7 0 14 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 图１１.2.5 某人从图的左上角的Ａ点出发，可以向下行走，也可以向右走，直到到达右下角的Ｂ点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字０）。此人从Ａ点到Ｂ点共走两次，试找出２条这样的路径，使得取得的数之和最大。 输入 输入的第一行为一个整数Ｎ（表示Ｎ＊Ｎ的方格图），接下来的每行右三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的０表示输入结束。 输出 只需输出一个整数，表示２条路径上取得的最大的和 样例输入 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 样例输出 67 题解 我们对这道题并不陌生。如果求一条数和最大的路径，读者自然会想到动态程序设计方法。现在的问题是，要找出这样的两条路径，是否也可以采用动态程序设计方法呢？回答是可以的。 1.状态的设计 我们衡量一个算法的标准，无外乎时间、空间两项指标。“动态规划”算法的时间大多数为“多项式级”，比起同样解决这个问题的有哪些信誉好的足球投注网站算法“指数级”的时间来说，“动态规划”的时间需要是很少的，所以我们在实际应用中，很少考虑“动态规划”算法的时间问题，而最经常考虑的是空间问题：即状态的设计与存储。对于一个“动态规划”算法来说，状态的设计与存储比阶段的划分更重要，因为阶段只是一些可以等同处理的状态的集合（例如，可以将两条路径走第i步的所有可能位置定义为一个阶段）。所以，状态的选定对整个问题的处理起了决定性的作用。我们选定的状态必须满足如下两点： 1：状态必须完全描述出事物的性质，两个不同事物的状态是不同的； 2：必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。 状态是描述事物性质的量，所以我们应该以上述要求为标准，根据方格取数问题的具体情况来具体分析： 我们从（1，1）出发，每走一步作为一个阶段，则可以分成2*n-1个阶段： 第一个阶段，两条路径从（1，1）出发； 第二个阶段，两条路径可达（2，1）和（1，2）； 第三个阶段，两条路径可达的位置集合为（3，1）、（2，2）和（1，3）； ………………………… 第2*n-1个阶段，两条路径汇聚（n，n）； 在第k(1≤k≤2*n-1)个阶段，两条路径的终端坐标（x1，y1）（x2，y2.2.6所示： 图１１.2.6 如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的x坐标（x1，x2）作状态，其中 （1≤x1≤k）∧（x1{1..n}）∧（1≤x2≤k）∧（x2{1..n}） 直接由x坐标计算对应的y坐标： （y1=k+1-x1）∧（y1{1..n}）∧（y2=k+1-x2）∧（y2{1..n}） 2.状态转移方程 设两条路径在k阶段的状态为（x1，x2）。由（y1=k+1-x1）∧（y1{1..n}）得出第一条路径的坐标为（x1，y1）；由（y2=k+1-x2）∧（y2{1..n}）得出第二条路径的坐标为（x2，y2）。假设在k-1阶段，两条路径的状态为（x1’，x2’）且（x1’，x2’）位于（x1，x2）状态的左邻或下邻位置。因此我们设条路径的延伸方向为d1和d2：di=0，表明第i条路径由（xi’，yi’）向右延伸至（xi，yi）；di=1，表明第i条路径由（xi’，yi’）向下延伸至（xi，yi）（1≤i≤2）。显然（x1’= x2’）∧（d1= d2），表明两条路径重合，同时取走了（x1’，y1’）和（x1，y1）中的数，这种取法当然不可能得到最大数和的。 分析两种可能： ⑴若x1=x2，x1状态，可取走（x1，y1）中的数(图11.2.