算法

(DFS+DP) $O(2^n*n^2)$

（1）这题数据非常小，做法自由
（2）首先第一趟可以dfs所有情况，从右上走到左下
（3）然后，走过的地方将a[i][j]修改为0，再走下一个点，之后要记得改回来。
（4）对于每一种右上角到左下角的走法，在改变了方格数的基础上，然后进行一次DFS，每次记录总的最大值
（5）最大值就是解

时间复杂度

（1）DFS方格：2^n
（2）DP：n^2
（3）总的：O(2^n*n^2)

Python3 代码

#[Python3]dfs+dp

n = int(input())
a = [[0 for i in range(n + 2)] for j in range(n + 2)]

while True:
    i, j, w = map(int, input().split())
    if i == 0 and j == 0 and w == 0: break
    a[i][j] = w

ans = 0


def dp(res):
    global ans

    f = [[0 for i in range(n + 2)] for j in range(n + 2)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]
    ans = max(res + f[n][n], ans)

def dfs(x, y, res):
    t=a[x][y]
    a[x][y]=0
    if x == n and y == n:
        dp(res)
        a[x][y]=t
        return

    if x + 1 <= n and y <= n:
        dfs(x + 1, y, res + a[x+1][y])
    if y + 1 <= n and x <= n:
        dfs(x, y + 1, res + a[x][y+1])

    a[x][y]=t

dfs(1, 1, a[1][1])
print(ans)