方格取数问题python

方格取数问题是一个经典的动态规划问题。给定一个 $n \times n$ 的方格矩阵，每个格子里有一个整数。从左上角开始，每次只能向下或向右走一步，走过的格子里的数字累加起来，问从左上角走到右下角，所有可能的路径中，数字之和的最大值是多少？

下面是一个 Python 实现：

def max_sum(n, grid):
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = grid[0][0]
    for i in range(1, n):
        dp[0][i] = dp[0][i-1] + grid[0][i]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[n-1][n-1]

n = 3
grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]

print(max_sum(n, grid))  # 输出：12

这个算法的时间复杂度是 $O(n^2)$，空间复杂度也是 $O(n^2)$。