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

输入: grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

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

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

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

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

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

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