穿越障碍：最小路径和的高效算法比较【python力扣题64】

本文主要是介绍穿越障碍：最小路径和的高效算法比较【python力扣题64】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
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

---

方法一：动态规划

解题步骤

1. 定义状态：创建一个同样大小的二维数组 dp，其中 dp[i][j] 表示到达点 (i, j) 的最小路径和。
2. 初始化状态：第一行和第一列的元素只能由它的左边或上边来，所以是累加当前行或列的值。
3. 状态转移：对于其他位置，dp[i][j] 由它的左边和上边的较小值加上当前网格值得到，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
4. 返回结果：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))，使用了一个同样大小的二维数组。

方法二：空间优化的动态规划

解题步骤

1. 使用一维数组：只用一个长度为 n 的数组来保存当前行的 dp 值。
2. 迭代更新：每次更新时，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] * ndp[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 的数组。

方法三：递归 + 记忆化

解题步骤

1. 递归定义：定义一个递归函数，用于计算到达 (i, j) 的最小路径和。
2. 记忆化存储：使用一个字典或数组来存储已经计算过的结果，避免重复计算。

完整的规范代码

def minPathSum(grid):"""使用递归和记忆化搜索解决最小路径和问题:param grid: List[List[int]], 网格:return: int, 最小路径和"""from functools import lru_cachem, 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))，记忆化需要的空间。

方法四：从终点到起点的动态规划

解题步骤

1. 反向动态规划：从网格的右下角开始，向左上角逐步计算。
2. 更新规则：每个点的最小路径和取决于其右边和下边的点的最小路径和。

完整的规范代码

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

解题步骤

1. 队列实现BFS：使用队列来实现广度优先搜索，每次处理一层。
2. 累计最小和：使用额外的二维数组来保存到每个点的最小路径和。
3. 优先队列优化：使用优先队列（小顶堆）来优先处理当前路径和最小的节点，以快速找到最小路径和。

完整的规范代码

from heapq import heappush, heappopdef 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 + dyif 0 <= nx < m and 0 <= ny < n:new_cost = cost + grid[nx][ny]if new_cost < costs[nx][ny]:costs[nx][ny] = new_costheappush(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来快速调整路径，以应对动态变化的环境条件，如临时障碍或优先级任务。

这篇关于穿越障碍：最小路径和的高效算法比较【python力扣题64】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---