1639: 蓝桥杯算法训练VIP-方格取数（Python3）两种解法，时间复杂度O(n^4)和O(n^3)

解题思路:
DP

注意事项:
方法二跳过0索引避免出错，不过好像也可以不跳，我不会

参考代码:

方法1：时间复杂度高，容易理解

N = int(input())
maps = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp = [[[[0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N+1)] for _ in range(N +1)]
while 1:
    nums = list(map(int, input().split()))
    if sum(nums):
        maps[nums[0]][nums[1]] = nums[2]
    else:
        break

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            for m in range(1, N + 1):
                temp = maps[i][j] if i == k and j == m else maps[i][j] + maps[k][m]
                dp[i][j][k][m] = max(dp[i-1][j][k-1][m], dp[i][j-1][k][m-1],
                                     dp[i-1][j][k][m-1], dp[i][j-1][k-1][m]) + temp
print(dp[-1][-1][-1][-1])

方法2：方法1的优化版本

N = int(input())
maps = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp = [[[0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + N + 1)]
while 1:
    nums = list(map(int, input().split()))
    if sum(nums):
        maps[nums[0]][nums[1]] = nums[2]
    else:
        break
dp[2][1][1] = maps[1][1]
for i in range(2, N + N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            temp_0, temp_1 = i - j, i - k
            if 1 <= temp_0 <= N and 1 <= temp_1 <= N:
                temp = maps[j][temp_0] if j == k else maps[j][temp_0] + maps[k][temp_1]
                dp[i][j][k] = max(dp[i-1][j][k-1], dp[i-1][j-1][k],
                                     dp[i-1][j][k], dp[i-1][j-1][k-1]) + temp
print(dp[-1][-1][-1])