方格取数问题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)$。

相关问题

网络流方格取数问题python代码

下面是一个简单的 Python 代码实现方格取数问题的网络流解法：

from collections import deque

# 定义网络流节点
class Node:
    def __init__(self, x, y, val):
        self.x = x
        self.y = y
        self.val = val
        self.in_edges = []
        self.out_edges = []

# 定义网络流边
class Edge:
    def __init__(self, u, v, cap, flow):
        self.u = u
        self.v = v
        self.cap = cap
        self.flow = flow
        self.rev = None

# 构建网络流图
def build_graph(grid):
    n = len(grid)
    m = len(grid[0])
    nodes = [[None] * m for _ in range(n)]
    s = Node(-1, -1, 0)
    t = Node(-2, -2, 0)
    for i in range(n):
        for j in range(m):
            nodes[i][j] = Node(i, j, grid[i][j])
            if (i + j) % 2 == 0:
                # 如果是偶数行，向源点连边
                e = Edge(s, nodes[i][j], nodes[i][j].val, 0)
                e.rev = Edge(nodes[i][j], s, 0, 0)
                e.rev.rev = e
                s.out_edges.append(e)
                nodes[i][j].in_edges.append(e)
            else:
                # 如果是奇数行，向汇点连边
                e = Edge(nodes[i][j], t, nodes[i][j].val, 0)
                e.rev = Edge(t, nodes[i][j], 0, 0)
                e.rev.rev = e
                t.in_edges.append(e)
                nodes[i][j].out_edges.append(e)
            if i > 0:
                # 向上连边
                e = Edge(nodes[i][j], nodes[i-1][j], min(nodes[i][j].val, nodes[i-1][j].val), 0)
                e.rev = Edge(nodes[i-1][j], nodes[i][j], 0, 0)
                e.rev.rev = e
                nodes[i][j].out_edges.append(e)
                nodes[i-1][j].in_edges.append(e)
            if j > 0:
                # 向左连边
                e = Edge(nodes[i][j], nodes[i][j-1], min(nodes[i][j].val, nodes[i][j-1].val), 0)
                e.rev = Edge(nodes[i][j-1], nodes[i][j], 0, 0)
                e.rev.rev = e
                nodes[i][j].out_edges.append(e)
                nodes[i][j-1].in_edges.append(e)
    return nodes, s, t

# 计算最大流
def max_flow(nodes, s, t):
    total_flow = 0
    while True:
        # 使用 BFS 寻找增广路径
        q = deque()
        q.append(s)
        parent = {s: None}
        while q and t not in parent:
            u = q.popleft()
            for e in u.out_edges:
                if e.v not in parent and e.flow < e.cap:
                    parent[e.v] = e
                    q.append(e.v)
            for e in u.in_edges:
                if e.u not in parent and e.flow > 0:
                    parent[e.u] = e.rev
                    q.append(e.u)
        if t not in parent:
            break
        # 计算增广路径上的最小残量
        path_flow = float("inf")
        v = t
        while v != s:
            e = parent[v]
            path_flow = min(path_flow, e.cap - e.flow if e.u == v else e.flow)
            v = e.u if e.u != v else e.v
        # 更新网络流
        v = t
        while v != s:
            e = parent[v]
            if e.u == v:
                e.flow += path_flow
            else:
                e.flow -= path_flow
            v = e.u if e.u != v else e.v
        total_flow += path_flow
    return total_flow

# 方格取数问题的解法
def max_sum(grid):
    nodes, s, t = build_graph(grid)
    max_flow(nodes, s, t)
    return sum(nodes[i][j].val for i in range(len(nodes))
               for j in range(len(nodes[0]))
               if (i + j) % 2 == 0 and nodes[i][j] in s.out_edges)

其中，`build_graph` 函数用于构建网络流图，`max_flow` 函数用于计算最大流，`max_sum` 函数用于计算方格取数问题的最大和。

方格取数问题python语言的数学建模

方格取数问题是一道经典的数学问题，可以用Python语言进行数学建模求解。

问题描述：

在一个 $n$ 行 $m$ 列的方格中，每个方格内填有一个正整数。从左上角出发，每次只能向右或向下走一格，直到到达右下角。求出一条路径，使路径上经过的数字之和最小。

建模思路：

1. 定义二维数组 $dp$，其中 $dp[i][j]$ 表示从左上角到第 $i$ 行第 $j$ 列的最小路径和。
2. 状态转移方程：$dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$，其中 $grid[i][j]$ 表示第 $i$ 行第 $j$ 列的数字。
3. 最终答案为 $dp[n-1][m-1]$。

Python代码实现：

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[-1][-1]

这样，我们就可以用Python语言对方格取数问题进行数学建模求解了。