动态规划[入门]3-更难的矩阵取数问题

时间：2015-10-12 12:22:26 阅读：266 评论：0 收藏：0 [点我收藏+]

分析：只走一次的问题我们之前分析过。现在要走两次，有什么好办法呢？我们设想，有两个人都从左上角走到右下角，这和走到终点再返回是一样的，我们可以dp么？怎么dp?先看看按照之前那种方法dp两次行不行？看下图：

如果第一条路径先找最优的，就要走路径(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)。
技术分享

但是这样(1,5)和(5,3)的两个100就分开了，第二条路径至多取到一个100。事实上，我们可以选取这样的两条路径：

(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)

这两条路径取得了全部的100，这两条路径是最优的！

没招了么？其实我们可以“两个人一起”dp（让两个人同时走）。

用dp[x1][y1][x2][y2]表示第一个人在(x1,y1) 并且第二个人在(x2,y2)时的最大值。

我们有初值dp[1][1][1][1] = a[1][1]，求的是dp[m][n][m][n]。

问题来了：每个人走一步，状态转移是什么？

dp[x1][y1][x2][y2] = max{dp[x1’][y1’][x2’][y2’]} + a[x1][y1] + a[x2][y2]
其中(x1’,y1’)是(x1,y1)的邻居，(x2’,y2’)是(x2,y2)的邻居。

事实上，因为我们有这个等式提示我们其实只要用3维就可以表示这个矩阵，因为 y2 = x1 + y1 – x2所以那一维可以用走多少步表示出来。

dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1] + a[x2][y2]

图中为step做了编号。

然而这个dp并没有体现出走到相同格子，数字仅计算一次的要求。那么我们加上这个条件：如果x1 = x2，dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1]。

最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。

输入

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)
第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

输出

输出能够获得的最大价值。

输入示例

输出示例

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

原文：http://www.cnblogs.com/nbalive2001/p/4871178.html

踩

(1)

(0)

评论一句话评论（0）

分享档案

更多>