因为从左上到右下要找到两条路径,还不能重合,所以我们直接从左上到右下,开四维数组,前两个和后两个分别从上一行、上一列进行转移,然后取最大值并且加上到的那个点的值,如果算重了就减去,最后输出就行。下边说一下具体的状态:
定义\(f[i][j][k][l]\)为一条路径到\(i\)行\(j\)列,另一条到\(k\)行\(l\)列得到的最大值,状态转移如下:
\[f[i][j][k][l] = max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l]; \]