方格取数
给出N*N的方格图,方格中填入某些正整数,某些是0。
让你从左上角出发,走到右下角。
两种方式:可以向下,向右走。
问你走两次,找出两条路径,使得的数字和最大。

解题:
思考之前的题目是走一次,类似题目摘花生和最低通行费。

对于这个新的问题,我们先以以前的思考来类别
摘花生
f[i][j] 表示从(1,1)到(n,n)的路径的最大值
f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
需要注意的是这个是取一次

状态表示

对于目前这个题目,首先走两次,那么路线可能会有重复点。
走两次:
f[i1,j1][i2,j2] 表示所有从(1,1)(1,1)分别走到(i1,j1)(i2,j2)的路径最大值

如何处理”同一个格子不能被重复选择“
我们可以考虑到,只有i1+j1 == i2+j2时两条路径的格子才可以重和。
同时走,只有相等的时候才会在同一个格子里。

这个我们要想不重复,那么我们可以考虑一边走一边标记,或者说两个同时走,
对于DP上,我们可以考虑两个同时走的情况。
假如,f[k,i1,i2] 表示所有从 分别走到(i1,k-i1)(i2,k-i2)的路径的最大值。

k 表示两条路线当前走到的格子的横纵坐标之和
k=i1+j1 =i2+j2
状态计算

关于这个
第一条 下 第一条 下 第一条:右 第一条:右
第二条 下 第二条 右 第二条:下 第二条:右