1611: 蓝桥杯算法训练VIP-传纸条（Python3）三维DP

解题思路:
类似题目：https://www.dotcpp.com/oj/problem1639.html    题解：https://blog.dotcpp.com/a/77794

参考：http://www.voidcn.com/article/p-xlafzyov-bqa.html

注意事项:
Python用四维DP会超时

参考代码:

1.

rows, cols = map(int, input().split())
students = [[0 for _ in range(cols + 1)]] + [[0] + list(map(int, input().split())) for _ in range(rows)]
dp = [[[0 for _ in range(rows + 1)] for _ in range(rows + 1)] for _ in range(rows + cols + 1)]

for i in range(2, rows + cols + 1):
    for j in range(1, rows + 1):
        for k in range(1, rows + 1):
            temp_0, temp_1 = i - j, i - k
            if 1 <= temp_0 <= cols and 1 <= temp_1 <= cols:
                temp = students[j][temp_0] + students[k][temp_1] if j != k else students[j][temp_0]
                dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - 1],
                                  dp[i - 1][j][k - 1], dp[i - 1][j - 1][k]) + temp
print(dp[-1][-1][-1])

2.

rows, cols = map(int, input().split())
students = [list(map(int, input().split())) for _ in range(rows)]
dp = [[[0 for _ in range(rows)] for _ in range(rows)] for _ in range(rows + cols - 1)]

for i in range(1, rows + cols - 1):
    for j in range(rows):
        for k in range(rows):
            temp_0, temp_1 = i - j, i - k
            if 0 <= temp_0 < cols and 0 <= temp_1 < cols:
                temp = students[j][temp_0] + students[k][temp_1] if j != k else students[j][temp_0]
                dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - 1],
                                  dp[i - 1][j][k - 1], dp[i - 1][j - 1][k]) + temp
print(dp[-1][-1][-1])