题目：

题意：

给定一个m*n的矩阵，从（1，1）向下或向右走到（m,n)之后向上或向左走回（1,1)，要求路径中每个点都不重复。

问使得权值和最大的路径的权值是多少。

思路：

这道题要学会把问题转化成，找两条从(1,1)到(m, n)互不相交的路径。因为过去和回来其实是相对的。

如果用一个四维dp，dp[i][j][k][l]表示从(1,1)到(i,j)的路径和从(1,1)到(k,l)的路径，他们互不相交的最大权值和。

分别枚举i,j,k,l, dp[i][j][k][l] = max(dp[i][j-1][k-1][l], dp[i-1][j][k-1][l], dp[i-1][j][k][l-1], dp[i][j-1][k][l-1])+g[i][j]+g[k][l]

当(i,j)==(k,l)时，这个点的权值只能算一次。

我们可以发现他走的方向规定之后，代表步数是一定的。因此我们可以缩减一维。

dp[step][i][j]就表示用step步，走到第i行和第j行时的两条互不相交路径的最大权值和。

1 #include
     
       2 #include
      
        3 #include