作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
1. 问题介绍和应用场景
最小路径和问题是一个常见的动态规划问题，涉及在给定的二维网格上找到一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。这个问题在实际中可以应用于如物流、路径规划、资源分配等多个领域，特别是在需要最优化资源消耗的情况下。
2. 问题定义和示例
定义：给定一个包含非负整数的 m x n 网格 grid，找到一条从左上角到右下角的路径，使得路径上的数字总和为最小。
示例：
给定网格：
[ [1, 3, 1], [1, 5, 1], [4, 2, 1] ]
最小路径和为 7（路径 1→3→1→1→1）。
3. 状态定义
定义 dp[i][j] 为到达网格中 (i, j) 位置的最小路径和。
4. 状态转移方程
状态转移方程基于只能向右或向下移动的规则：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
这里，dp[i-1][j] 表示从上方来的最小路径和，dp[i][j-1] 表示从左方来的最小路径和。
5. 初始化和边界情况
dp[0][0] = grid[0][0]，作为起点。- 第一行的每个位置只能从左边来，第一列的每个位置只能从上方来：
dp[0][j] = dp[0][j-1] + grid[0][j] # 第一行 dp[i][0] = dp[i-1][0] + grid[i][0] # 第一列
6. 算法实现
def min_path_sum(grid): """ 计算给定网格从左上角到右下角的最小路径和。每次只能向右或向下移动。 参数: grid (List[List[int]]): 二维列表，每个元素代表网格中的一个点的值。 返回: int: 从左上角到右下角的最小路径和。 """ if not grid or not grid[0]: return 0 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] # 填充剩余的dp表 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]) return dp[-1][-1] # 返回右下角的最小路径和 # 示例 grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] print("最小路径和:", min_path_sum(grid)) # 输出: 最小路径和: 7
代码解释
- 函数定义：min_path_sum 函数接受一个二维列表 grid，其中 grid[i][j] 表示网格中第 i 行第 j 列点的值。
- 边界情况处理：如果输入的 grid 为空或者其第一行为空，函数返回0。
- 动态规划数组初始化：创建一个同样大小的二维列表 dp，其中 dp[i][j] 用于存储从网格的左上角到位置 (i, j) 的最小路径和。dp[0][0] 初始化为 grid[0][0]，即起点的路径和。
- 初始化 dp 的第一行和第一列：由于第一行的每个位置只能从左边来，第一列的每个位置只能从上面来，这两行分别累加初始化。
- 填充 dp 表：从 dp[1][1] 开始，计算每个点的最小路径和，依赖于其左边和上面的点的最小路径和。
- 返回结果：函数返回 dp 表最后一个元素，即 dp[-1][-1]，它代表了从起点到终点的最小路径和。
7. 复杂度分析
- 时间复杂度：O(mn)，因为需要遍历整个网格一次。
- 空间复杂度：O(mn)。可以优化至 O(min(m, n)) 通过滚动数组或两行交替使用的技术。
为了进一步阐明最小路径和问题的动态规划解法，并以图解的方式展示算法的实际运作，我们将继续使用前述的例子并详细解释每一步的计算过程。
8.算法图解
动态规划表的初始化与填充
首先，我们初始化动态规划表（dp 表）。表的每个单元格代表到达该位置的最小路径和。
初始化阶段
- 起始点：
dp[0][0]初始化为网格的起始点，grid[0][0] = 1。 - 第一行：每个位置只能从左边来，因此累加左边的值。
- 第一列：每个位置只能从上方来，因此累加上方的值。
初始化表格：
| 0 | 1 | 2 | |
| 0 | 1 | 4 | 5 |
| 1 | 2 | ||
| 2 | 6 |
填充过程
逐行填充，每个单元格的值是当前网格值加上到达该单元格的最小成本（从左方或上方来）。
- 填充第二行:
dp[1][1] = grid[1][1] + min(dp[1][0], dp[0][1]) = 5 + min(2, 4) = 7dp[1][2] = grid[1][2] + min(dp[1][1], dp[0][2]) = 1 + min(7, 5) = 6
- 填充第三行:
dp[2][1] = grid[2][1] + min(dp[2][0], dp[1][1]) = 2 + min(6, 7) = 8dp[2][2] = grid[2][2] + min(dp[2][1], dp[1][2]) = 1 + min(8, 6) = 7
完整填充的表格：
| 0 | 1 | 2 | |
| 0 | 1 | 4 | 5 |
| 1 | 2 | 7 | 6 |
| 2 | 6 | 8 | 7 |
最终的最小路径和为 dp[2][2] = 7，路径是 1→3→1→1→1。
9.总结
最小路径和问题通过动态规划提供了一种高效的解决方案，适用于多种实际场景。通过本文的解析，我们展示了如何逐步构建解决方案，从基本的状态定义到复杂的状态转移，以及如何从实际问题中抽象出适用的动态规划模型。这不仅帮助理解动态规划的运作机制，也提供了实现高效算法的基础
欢迎关注微信公众号 数据分析螺丝钉
