穿越障碍:最小路径和的高效算法比较【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] * 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 的数组。

方法三:递归 + 记忆化

解题步骤
  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
算法分析
  • 时间复杂度:(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, 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来快速调整路径,以应对动态变化的环境条件,如临时障碍或优先级任务。

欢迎关注微信公众号 数据分析螺丝钉

目录
打赏
0
2
2
0
68
分享
相关文章
解锁文档管理系统高效检索奥秘:Python 哈希表算法探究
在数字化时代,文档管理系统犹如知识宝库,支撑各行各业高效运转。哈希表作为核心数据结构,通过哈希函数将数据映射为固定长度的哈希值,实现快速查找与定位。本文聚焦哈希表在文档管理中的应用,以Python代码示例展示其高效检索特性,并探讨哈希冲突解决策略,助力构建智能化文档管理系统。
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
50 9
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
49 12
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
43 10
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
62 17
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
216 5
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
139 66
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
87 0

热门文章

最新文章