动态规划-方格取数思考解题方式

方格取数
给出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
状态计算

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