更难的矩阵取数问题（dp）

本文主要是介绍更难的矩阵取数问题（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

更难的矩阵取数问题

分析： 只走一次的问题我们之前分析过。现在要走两次，有什么好办法呢？ 我们设想，有两个人都从左上角走到右下角，这和走到终点再返回是一样的，我们可以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)

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

3 3
1 3 3
2 1 3
2 2 1

17

代码：

#include<iostream>
#include<cstring>
using namespace std;int dp[405][205][205];  //放在main()里会崩，因为数组太大
int a[205][205];  //放里面一个超大的数据过不了int main()
{int m,n;cin>>m>>n;for(int i=0;i<n;i++){for(int j=0;j<m;j++)cin>>a[i][j];}memset(dp,0,sizeof(dp));dp[0][0][0]=a[0][0];int x1,y1,x2,y2;for(int i=1;i<n+m;i++){for(x1=0;x1<n&&i-x1>=0;x1++){for(x2=0;x2<n&&i-x2>=0;x2++){if(x1>=1&&x2>=1)  //不在起点dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2>=1)  //x1不动，x2动。  即x1代表向右走，x2向下走dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1>=1&&x2<=i-1)  //x1动，x2不动。dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2<=i-1)  //x1、x2都不动dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));}}}cout<<dp[n+m-1][n-1][n-1]<<endl;return 0;
}

这篇关于更难的矩阵取数问题（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！