使用二阶动态规划解决方格取数

题目描述

设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B

某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

解法

这是典型的动态规划方法，因为每一步的选择影响了下一步的结果。

又因为要找出两条路径之和为最大，所以是一个2维的动态规划问题。

动态规划的典型套路可以总结成：

1. 定义一个变量代表要求的值。本题中就是从A到B两条路径之和。

2. 动态判断该变量的取值。动态的核心就是每次要判断当前变量的取值，一般会出现v = max(v, w)，其中w是另外一种计算出v的方法，例如本题中到B点可以有不同的路径，所以要比较不同的路径。

套路有了，下面就是具体的求解了。

1. 由于是2维动态规划，所以变量是一个四维的数组：D[p1, p2]代表了A到点p1与A到p2的两条路径的最大值。

2. 动态更新：从A点开始，发出两条路径，每个点向右或者向下。如下图所示，当前层是p1、p2，下一层是四个可能的点q1、q2、q3、q4，那么就可以更新D[q1, q2]、D[q1, q3]、D[q2, q3]、D[q2, q4]这四个值了。比如

D[q1, q3] = max(D[q1, q3]，D[p1, p2] + M[q1] + M[q3])

关键的就是要判断从其他路径到达q1、q3两个点的D[q1, q3]（当前的取值）和通过p1, p2两个点到达q1、q3的值（D[p1, p2] + M[q1] + M[q3])哪个是最大的。

注意到题目中的另外一个约束条件：方格中的数会被取走，所以还需要考虑q1, q2, q3, q4之间有重合的情况：

 这种下需要更新的是D[q1, q2]，D[q1, q3]、D[q2, q2]、D[q2, q3]这四个值，

对于D[q2, q2] 的更新方法为：

D[q2, q2] = max(D[q2, q2],   D[p1,p2] + M[q2]）

代码

import numpy as np
N = int(input())
M = np.zeros((N, N))

while 1:
    t = list(map(int, input().split()))
    if np.sum(t) > 0:
        M[t[0] - 1, t[1] - 1] = t[2]
    else:
        break

# max_v中的每个点的值代表的是从A点到两个点的两条路径的最大值
max_v = np.zeros((N,N,N,N))

# 初始化, v1_list是到p1_list中的每个点的最大值
p1_list = [[0, 1]]
v1_list = [M[0, 0] + M[0, 1]]
p2_list = [[1, 0]]
v2_list = [M[0, 0] + M[1, 0]]
max_v[0,0,0,0] = M[0, 0]
max_v[0,0,0,1] = M[0,0] + M[0, 1]
max_v[0,0,1,0] = M[0,0] + M[1, 0]
max_v[0,1,0,0] = M[0,0] + M[0, 1]
max_v[1,0,0,0] = M[0,0] + M[1, 0]
max_v[1,0,0,1] = M[0,0] + M[1, 0] + M[0, 1]
max_v[0,1,1,0] = max_v[1,0,0,1]

while len(p1_list) > 0 or len(p2_list) > 0:
    
    
    new_p1_list = []
    new_v1_list = []
    new_p2_list = []
    new_v2_list = []
    
    for i in range(len(p1_list)):
        p1 = p1_list[i]
        tmp_p1_list = []
        if p1[0] < N - 1:            
            p1_right = [p1[0] + 1, p1[1]]
            tmp_p1_list.append(p1_right)  
            new_p1_list.append(p1_right)

        if p1[1] < N - 1:
            p1_down = [p1[0], p1[1] + 1]
            tmp_p1_list.append(p1_down)
            new_p1_list.append(p1_down)  
            
            
        for j in range(len(p2_list)):
            p2 = p2_list[j]
            tmp_p2_list = []  
            
            if p2[0] < N - 1:            
                p2_right = [p2[0] + 1, p2[1]]
                tmp_p2_list.append(p2_right)
                
                if p2_right not in new_p2_list:
                    new_p2_list.append(p2_right)    

            if p2[1] < N - 1:
                p2_down = [p2[0], p2[1] + 1]
                tmp_p2_list.append(p2_down)
                
                if p2_down not in new_p2_list:
                    new_p2_list.append(p2_down)
            
        
            for l in range(len(tmp_p1_list)):
                for k in range(len(tmp_p2_list)):
                    new_p1 = tmp_p1_list[l]                    
                    new_p2 = tmp_p2_list[k]
                    
                    t = max_v[new_p1[0], new_p1[1], new_p2[0], new_p2[1]]
                     
                    if new_p1[0] == new_p2[0] and new_p1[1] == new_p2[1]:
                        max_v[new_p1[0], new_p1[1], new_p2[0], new_p2[1]] = max(t, max_v[p1[0], p1[1], p2[0], p2[1]] + M[new_p1[0], new_p1[1]])
                    else:
                        max_v[new_p1[0], new_p1[1], new_p2[0], new_p2[1]] = max(t, max_v[p1[0], p1[1], p2[0], p2[1]] + M[new_p1[0], new_p1[1]] + M[new_p2[0], new_p2[1]])
                    
                    #print(new_p1[0], new_p1[1], new_p2[0], new_p2[1], max_v[new_p1[0], new_p1[1], new_p2[0], new_p2[1]])
                    
    p1_list = new_p1_list
    p2_list = new_p2_list
    v1_list = new_v1_list
    v2_list = new_v2_list
        

print(int(max_v[N-1,N-1,N-1,N-1]))