穿越障碍：最小路径和的高效算法比较【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 的总和最小。
1
2
3
4
5
6
7

示例 2

输入: grid = [
  [1,2,3],
  [4,5,6]
]
输出: 12
1
2
3
4
5

---

方法一：动态规划

解题步骤

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

算法分析

• 时间复杂度：(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] * 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

算法分析

• 时间复杂度：(O(m * n))，需要遍历整个网格一次。
• 空间复杂度：(O(n))，使用了一个长度为列数 n 的数组。

方法三：递归 + 记忆化

解题步骤

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

完整的规范代码

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

算法分析

• 时间复杂度：(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法分析

• 时间复杂度：(O(m * n))，需要遍历整个网格一次。
• 空间复杂度：(O(1))，直接在输入网格上进行修改，不需要额外空间。

方法五：改进的BFS

解题步骤

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

完整的规范代码

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

算法分析

• 时间复杂度：(O(m * n \log(m * n)))，每个节点可能多次进入堆。
• 空间复杂度：(O(m * n))，用于存储路径成本和堆结构。

不同算法的优劣势对比

应用示例

机器人导航系统：
在自动化仓库或智能制造系统中，机器人需要找到成本最低的路径来移动货物或执行任务。动态规划方法可以有效地计算出从起点到终点的最低成本路径，提高系统的效率和响应速度。此外，实时路径规划系统可以利用优先队列优化的BFS来快速调整路径，以应对动态变化的环境条件，如临时障碍或优先级任务。