在Python中，使用动态规划解决涉及二维数组的问题时，通常会创建一个二维数组 `dp` 来存储子问题的解，其中 `dp[i][j]` 表示到达位置 `(i, j)` 的最小路径和或其他目标值。为了正确实现动态规划算法，需要注意以下几点： ### 初始化二维数组 动态规划的初始化通常涉及设置第一行和第一列的值，因为这些位置的值通常是固定的，或者可以通过简单的逻辑推导得出。例如，对于最小路径和问题，第一行和第一列的路径和只能是从起点连续向右或向下移动的结果。 初始化可以通过以下几种方式实现： ```python # 假设输入的二维数组为 grid，其大小为 m x n m, n = len(grid), len(grid[0]) # 创建一个 m x n 的二维数组 dp，初始值为 0 dp = [[0] * n for _ in range(m)] # 设置起点的值 dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] ``` ### 状态转移方程 状态转移方程用于计算 `dp[i][j]` 的值，通常依赖于 `dp[i-1][j]` 和 `dp[i][j-1]` 的值。例如，在最小路径和问题中，状态转移方程可以定义为： ```python for i in range(1, m): for j in range(1, n): dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]) ``` 此方程表示到达位置 `(i, j)` 的最小路径和等于当前位置的值加上从上方或左方到达的最小路径和中的较小值[^1]。 ### 路径记录 为了记录路径，可以使用另一个二维数组 `path` 来记录每一步的选择。例如，在最小路径和问题中，可以通过比较 `dp[i-1][j]` 和 `dp[i][j-1]` 的大小来决定是从上方还是左方到达当前位置： ```python # 创建一个 m x n 的二维数组 path，用于记录路径 path = [[(0, 0)] * n for _ in range(m)] # 在初始化过程中记录路径 for j in range(1, n): path[0][j] = (0, j - 1) for i in range(1, m): path[i][0] = (i - 1, 0) # 在状态转移过程中记录路径 for i in range(1, m): for j in range(1, n): if dp[i - 1][j] < dp[i][j - 1]: path[i][j] = (i - 1, j) else: path[i][j] = (i, j - 1) ``` ### 示例代码 以下是完整的动态规划实现，用于计算从二维数组左上角到右下角的最小路径和及其路径： ```python def min_path_sum(grid): m, n = len(grid), len(grid[0]) # 创建 dp 数组并初始化 dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] # 创建 path 数组并记录路径 path = [[(0, 0)] * n for _ in range(m)] for j in range(1, n): path[0][j] = (0, j - 1) for i in range(1, m): path[i][0] = (i - 1, 0) # 状态转移 for i in range(1, m): for j in range(1, n): if dp[i - 1][j] < dp[i][j - 1]: dp[i][j] = grid[i][j] + dp[i - 1][j] path[i][j] = (i - 1, j) else: dp[i][j] = grid[i][j] + dp[i][j - 1] path[i][j] = (i, j - 1) # 构建路径 i, j = m - 1, n - 1 min_path = [(i, j)] while (i, j) != (0, 0): i, j = path[i][j] min_path.append((i, j)) min_path.reverse() return dp[m - 1][n - 1], min_path ``` ###