算法训练 方格取数（多线程dp）
问题描述
设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出格式
只需输出一个整数，表示2条路径上取得的最大的和。
样例输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
样例输出
67
方法一：
思路：
从题意中我们可以知道这是一个像迷宫类型的题型，但我们可以知道题要求的是我们求出我们取出数值到终点的最大值，在这基础上是走2遍，然后把2遍取的方格数的和要最大值.那么我们可以先考虑用深层递归来求解。我们首先可以把从起点到终点模拟走完一次让在进入函数走一次，我们把所有可能全部走一次然后把最大值输出。
注意：我们第一次走的时候取的方格数要把他成为0，退回时记得回溯。
程序：
n=int(input())
a=[[0 for i1 in range(n+1)]for i in range(n+1)]
v=1
X=0
Y=0
while(v!=0): #XY 表示最大的x坐标和y坐标范围有值超过此范围的值都是0 用于走不必要的程序
v,v1,m=map(int,input().split())
X=v if X<v else X
Y=v1 if Y<v1 else Y
a[v][v1]=m
con=0
def bfs(x,y,su,f): #xy 表示当前的坐标， su表示当前的方格累计数f=0表示当前是第一次 f=1表示当前是第二次
global con
t=a[x][y]
a[x][y]=0 #已取走当前值
if x==X and y==Y: #到了边界值进入下个次数走
if f==1:
if con<su: # 要存最大值
con=su
else:
bfs(1,1,su,1) #第二次路线
if x<X:
bfs(x+1,y,su+a[x+1][y],f) #走右
if y<Y :
bfs(x,y+1,su+a[x][y+1],f)#走下
a[x][y]=t #回溯
bfs(1,1,a[1][1],0)
print(con)
方法二：
思路：
我们也可以用多线程dp，我们可以让2个人同时走然后把2个的值累计起来放在dp中，我们先建立4维dp。
dp[i][i1][j][j1]代表的含义是第一个人和第二个人同时走，第一个人走到（i, i1），第二个人走到（j, j1）时候的最大值。
dp[i-1][i1][j-1][j1]代表的含义是他们同时往下走 取出他们上一步的值
dp[i][i1-1][j][j1-1]代表的含义是他们同时往右走 取出他们上一步的值
dp[i-1][i1][j][j1-1]代表的含义是他们分别往下和右走 取出他们上一步的值
dp[i-1][i1][j-1][j1]代表的含义是他们分别往右和下走 取出他们上一步的值
程序：
n=int(input())
a=[[0 for i1 in range(n+1)]for i in range(n+1)]
v=1
dp=[[[[0 for i in range(10) ]for i in range(10) ] for i in range(10)] for i in range(10) ]
while(v!=0):
v,v1,m=map(int,input().split())
a[v][v1]=m
temp=0
dp[1][1][1][1]=a[1][1]
for i in range(1,n+1):# 第一个人的x轴
for i1 in range(1,n+1):#第一个人的y轴
for j in range(1,n+1):#第二个人的x轴
for j1 in range(1,n+1):#第二个人的y轴
if i1+i!=j+j1: #让他们是同步走的步数
continue
#他们分别往下或者右 或者同下和同右的 他们二个的最大值存到temp
temp=max(dp[i-1][i1][j-1][j1],dp[i-1][i1][j][j1-1])
temp=max(temp,dp[i][i1-1][j][j1-1])
temp=max(temp,dp[i][i1-1][j-1][j1])
if i==j and j1==i1: #如果他们的位置重合了 我们只加一次的计算量
dp[i][i1][j][j1]=temp+a[i][i1]
else: #否则就加他们不同位置取的方格
dp[i][i1][j][j1]=temp+(a[i][i1]+a[j][j1])
print(dp[n][n][n][n])
禁止转载。仅用于自己学习。对程序错误不负责。
