作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个包含非负整数的 m x n 网格 grid，现在你需要找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
注：每次只能向下或者向右移动一步。
输入格式
- grid：二维数组，其中的元素表示网格中的点的值。
输出格式
- 返回一个整数，表示所有可能路径中的最小和。
示例
示例 1
输入: grid = [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
示例 2
输入: grid = [ [1,2,3], [4,5,6] ] 输出: 12
方法一：动态规划
解题步骤
- 定义状态：创建一个同样大小的二维数组
dp，其中dp[i][j]表示到达点(i, j)的最小路径和。 - 初始化状态：第一行和第一列的元素只能由它的左边或上边来，所以是累加当前行或列的值。
- 状态转移：对于其他位置，
dp[i][j]由它的左边和上边的较小值加上当前网格值得到，即dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。 - 返回结果：
dp[m-1][n-1]即为最小路径和。
完整的规范代码
def minPathSum(grid): """ 使用动态规划解决最小路径和问题 :param grid: List[List[int]], 网格 :return: int, 最小路径和 """ 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[m-1][n-1] # 示例调用 print(minPathSum([ [1,3,1], [1,5,1], [4,2,1] ])) # 输出: 7 print(minPathSum([ [1,2,3], [4,5,6] ])) # 输出: 12
算法分析
- 时间复杂度：(O(m * n))，需要遍历整个网格一次。
- 空间复杂度：(O(m * n))，使用了一个同样大小的二维数组。
方法二：空间优化的动态规划
解题步骤
- 使用一维数组：只用一个长度为
n的数组来保存当前行的dp值。 - 迭代更新：每次更新时，
dp[j]更新为dp[j]（从上一行继承下来的，即上方）和dp[j-1]（当前行左边的，即左方）中的较小值加上当前点的值。
完整的规范代码
def minPathSum(grid): """ 使用一维数组进行动态规划，空间优化版本 :param grid: List[List[int]], 网格 :return: int, 最小路径和 """ m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] for i in range(1, m): dp[0] += grid[i][0] for j in range(1, n): dp[j] = min(dp[j-1], dp[j]) + grid[i][j] return dp[n-1] # 示例调用 print(minPathSum([ [1,3,1], [1,5,1], [4,2,1] ])) # 输出: 7 print(minPathSum([ [1,2,3], [4,5,6] ])) # 输出: 12
算法分析
- 时间复杂度：(O(m * n))，需要遍历整个网格一次。
- 空间复杂度：(O(n))，使用了一个长度为列数
n的数组。
方法三：递归 + 记忆化
解题步骤
- 递归定义：定义一个递归函数，用于计算到达
(i, j)的最小路径和。 - 记忆化存储：使用一个字典或数组来存储已经计算过的结果，避免重复计算。
完整的规范代码
def minPathSum(grid): """ 使用递归和记忆化搜索解决最小路径和问题 :param grid: List[List[int]], 网格 :return: int, 最小路径和 """ from functools import lru_cache m, n = len(grid), len(grid[0]) @lru_cache(None) def dfs(i, j): if i == 0 and j == 0: return grid[i][j] if i < 0 or j < 0: return float('inf') return grid[i][j] + min(dfs(i-1, j), dfs(i, j-1)) return dfs(m-1, n-1) # 示例调用 print(minPathSum([ [1,3,1], [1,5,1], [4,2,1] ])) # 输出: 7 print(minPathSum([ [1,2,3], [4,5,6] ])) # 输出: 12
算法分析
- 时间复杂度：(O(m * n))，每个点最多计算一次，利用记忆化避免重复计算。
- 空间复杂度：(O(m * n))，记忆化需要的空间。
方法四：从终点到起点的动态规划
解题步骤
- 反向动态规划：从网格的右下角开始，向左上角逐步计算。
- 更新规则：每个点的最小路径和取决于其右边和下边的点的最小路径和。
完整的规范代码
def minPathSum(grid): """ 使用反向动态规划解决最小路径和问题 :param grid: List[List[int]], 网格 :return: int, 最小路径和 """ m, n = len(grid), len(grid[0]) for i in range(m-2, -1, -1): grid[i][n-1] += grid[i+1][n-1] for j in range(n-2, -1, -1): grid[m-1][j] += grid[m-1][j+1] for i in range(m-2, -1, -1): for j in range(n-2, -1, -1): grid[i][j] += min(grid[i+1][j], grid[i][j+1]) return grid[0][0] # 示例调用 print(minPathSum([ [1,3,1], [1,5,1], [4,2,1] ])) # 输出: 7 print(minPathSum([ [1,2,3], [4,5,6] ])) # 输出: 12
算法分析
- 时间复杂度：(O(m * n))，需要遍历整个网格一次。
- 空间复杂度：(O(1))，直接在输入网格上进行修改，不需要额外空间。
方法五：改进的BFS
解题步骤
- 队列实现BFS：使用队列来实现广度优先搜索，每次处理一层。
- 累计最小和：使用额外的二维数组来保存到每个点的最小路径和。
- 优先队列优化：使用优先队列（小顶堆）来优先处理当前路径和最小的节点，以快速找到最小路径和。
完整的规范代码
from heapq import heappush, heappop def minPathSum(grid): """ 使用改进的BFS和优先队列解决最小路径和问题 :param grid: List[List[int]], 网格 :return: int, 最小路径和 """ m, n = len(grid), len(grid[0]) minHeap = [(grid[0][0], 0, 0)] # (cost, x, y) costs = [[float('inf')] * n for _ in range(m)] costs[0][0] = grid[0][0] while minHeap: cost, x, y = heappop(minHeap) for dx, dy in [(1, 0), (0, 1)]: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n: new_cost = cost + grid[nx][ny] if new_cost < costs[nx][ny]: costs[nx][ny] = new_cost heappush(minHeap, (new_cost, nx, ny)) return costs[m-1][n-1] # 示例调用 print(minPathSum([ [1,3,1], [1,5,1], [4,2,1] ])) # 输出: 7 print(minPathSum([ [1,2,3], [4,5,6] ])) # 输出: 12
算法分析
- 时间复杂度：(O(m * n \log(m * n)))，每个节点可能多次进入堆。
- 空间复杂度：(O(m * n))，用于存储路径成本和堆结构。
不同算法的优劣势对比
| 特征 | 方法一: 动态规划 | 方法二: 空间优化DP | 方法三: 递归+记忆化 | 方法四: 反向DP | 方法五: BFS+优先队列 |
| 时间复杂度 | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n \log(m * n))) |
| 空间复杂度 | (O(m * n)) | (O(n)) | (O(m * n)) | (O(1)) | (O(m * n)) |
| 优势 | 直观，易理解 | 空间效率高 | 避免重复计算，减少计算次数 | 不需要额外空间，原地修改 | 可以更快地找到最小路径和 |
| 劣势 | 空间占用高 | 仅限于列优化 | 需要辅助空间存储递归状态 | 修改输入数据 | 计算和空间复杂度较高 |
应用示例
机器人导航系统：
在自动化仓库或智能制造系统中，机器人需要找到成本最低的路径来移动货物或执行任务。动态规划方法可以有效地计算出从起点到终点的最低成本路径，提高系统的效率和响应速度。此外，实时路径规划系统可以利用优先队列优化的BFS来快速调整路径，以应对动态变化的环境条件，如临时障碍或优先级任务。
欢迎关注微信公众号 数据分析螺丝钉
