题意分析
在一个m行n列的矩阵中找到一条从(1,1)(1,1)(1,1)到(m,n)(m,n)(m,n)的路径和一条从(m,n)(m,n)(m,n)到(1,1)(1,1)(1,1)的路径，使得两条路径不相交且路径上的数值之和最大。
关键观察
无论是正向还是反向，都不影响结果，因此题目转化为找两条从(1,1)(1,1)(1,1)到(m,n)(m,n)(m,n)的不相交路径。计算两遍极其困难，题目数据范围仅有50，因此可设定第一维为步数，让两条路径同时前进。（注意，代码中的k表示的是步数+1，也可以理解为是经过的点数）同时，我们设定i和j用于表示当前步数下两条路径分别在i行和j行，若k-1步后一条路径在i行，则它一定位于k-i列，因为从数学上看，若只能向右或下方走，从(1,1)(1,1)(1,1)到(x,y)(x,y)(x,y)最少要x+yx+yx+y步。i和j的遍历覆盖了所有的可能性。再次观察，我们发现，若iii不变，kkk增加1，则路径列数（即k−ik-ik−i）增加1，这就是向右移动，若i跟着增加1，则是向下移动，j同理。因此若将矩阵中的权值储存在mp数组中，我们可列出转移方程：dp[k][i][j]=max(dp[k][i][j],dp[k−1][i][j],dp[k−1][i−1][j],dp[k−1][i][j−1],dp[k−1][i−1][j−1])+mp[i][k−i]+mp[j][k−j]dp[k][i][j]
= max(dp[k][i][j], dp[k-1][i][j], dp[k-1][i-1][j], dp[k-1][i][j-1], dp[k-1][i-1][j-1])+mp[i][k-i]+mp[j][k-j]dp[k][i][j]=max(dp[k][i][j],dp[k−1][i][j],dp[k−1][i−1][j],dp[k−1][i][j−1],dp[k−1][i−1][j−1])+mp[i][k−i]+mp[j][k−j]
虽然它已经长的有点诡异了，但是仍然有一个细节，我们要特判i==ji==ji==j的情况，防止一位同学加两次。可能有人会说题目明确说明了不能让一个同学传两次，但这正是这个问题的难点之一：可以证明，在网格图中，寻找两条不相交路径的最大和问题，等价于寻找两条允许交叉但不会真正"同时使用"同一节点的路径，通过特判 i == j 时只加一次值，实际上达到了"如果路径交叉，就相当于只使用了一次该同学"的效果。前人已经帮我们证明，在网格图中，如果存在两条相交的最优路径，总可以通过路径调整得到两条不相交的路径且和不变。
（如果你仍然不放心，我将在题解底部提供一个彻底防止路径重复和越界的代码，它同样可以达到AC的效果）
AC代码
特判重复
