跳到主要内容

二维动态规划

介绍​

动态规划（Dynamic Programming, DP）是一种用于解决复杂问题的算法技术，通过将问题分解为更小的子问题并存储子问题的解来避免重复计算。二维动态规划是动态规划的一种扩展形式，适用于那些需要处理二维数据结构（如矩阵或网格）的问题。

在二维动态规划中，我们通常会使用一个二维数组（或表格）来存储子问题的解。每个单元格的值通常依赖于其相邻单元格的值，从而逐步构建出最终的解。

基本概念​

状态定义​

在二维动态规划中，状态通常表示为 dp[i][j]，其中 i 和 j 是二维数组的索引。dp[i][j] 表示在位置 (i, j) 处的最优解或某种状态值。

状态转移方程​

状态转移方程是二维动态规划的核心。它定义了如何从已知的子问题的解推导出当前问题的解。通常，dp[i][j] 的值会依赖于 dp[i-1][j]、dp[i][j-1] 或 dp[i-1][j-1] 等相邻状态的值。

初始化​

在开始填充 dp 表之前，通常需要对边界条件进行初始化。例如，dp[0][0] 的值可能需要根据问题的具体要求进行设置。

最终解​

最终的解通常存储在 dp 表的某个特定位置，例如 dp[m-1][n-1]，其中 m 和 n 是二维数组的行数和列数。

实际案例：最小路径和问题​

让我们通过一个经典的二维动态规划问题——最小路径和问题，来深入理解这一概念。

问题描述​

给定一个 m x n 的网格，每个单元格中都有一个非负整数。你需要找到从左上角到右下角的一条路径，使得路径上的数字之和最小。每次只能向下或向右移动。

示例​

假设我们有以下网格：

[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

从左上角到右下角的最小路径和为 7，路径为 1 → 3 → 1 → 1 → 1。

解决思路​

  1. 状态定义：dp[i][j] 表示从 (0, 0) 到 (i, j) 的最小路径和。
  2. 状态转移方程：
    • 如果 i == 0 且 j == 0，dp[i][j] = grid[i][j]。
    • 如果 i == 0，dp[i][j] = dp[i][j-1] + grid[i][j]。
    • 如果 j == 0，dp[i][j] = dp[i-1][j] + grid[i][j]。
    • 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
  3. 初始化：dp[0][0] = grid[0][0]。
  4. 最终解：dp[m-1][n-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 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 表
    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[m-1][n-1]

输入和输出​

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

print(minPathSum(grid))  # 输出: 7

总结​

二维动态规划是一种强大的算法技术，适用于处理二维数据结构的问题。通过定义状态、建立状态转移方程、初始化边界条件以及填充 dp 表，我们可以有效地解决许多复杂的问题。

附加资源与练习​

  • 练习：尝试解决另一个经典的二维动态规划问题——最长公共子序列（LCS）。
  • 资源：阅读更多关于动态规划的书籍或在线教程，例如《算法导论》中的动态规划章节。
提示

在解决二维动态规划问题时，绘制 dp 表并手动填充几个单元格的值，可以帮助你更好地理解状态转移的过程。