本文主要是介绍穿越障碍：最小路径和的高效算法比较【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
方法一：动态规划
解题步骤
- 定义状态：创建一个同样大小的二维数组
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] * 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的数组。
方法三：递归 + 记忆化
解题步骤
- 递归定义：定义一个递归函数，用于计算到达
(i, j)的最小路径和。 - 记忆化存储：使用一个字典或数组来存储已经计算过的结果，避免重复计算。
完整的规范代码
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))，记忆化需要的空间。
方法四：从终点到起点的动态规划
解题步骤
- 反向动态规划：从网格的右下角开始，向左上角逐步计算。
- 更新规则：每个点的最小路径和取决于其右边和下边的点的最小路径和。
完整的规范代码
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, 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】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
