LeetCode 题目 62:不同路径【python】

简介: LeetCode 题目 62:不同路径【python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

题目描述

一个机器人位于一个 m x n 网格的左上角(起始点在下图标记为 “Start” )。机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角(在下图标记为 “Finish”)。问总共有多少条不同的路径?

输入格式
  • m:网格的行数。
  • n:网格的列数。
输出格式
  • 返回一个整数,表示所有可能的路径数量。

示例

示例 1
输入: m = 3, n = 7
输出: 28
示例 2
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

方法一:动态规划

解题步骤
  1. 初始化状态:创建一个二维数组 dp,其中 dp[i][j] 表示到达点 (i, j) 的路径数量。
  2. 边界条件:网格的第一行和第一列的路径数都是 1,因为只有一种方式到达(要么一直向右,要么一直向下)。
  3. 状态转移:对于其他位置,路径数 dp[i][j] 等于从左边来的路径数加上从上面来的路径数,即 dp[i][j] = dp[i-1][j] + dp[i][j-1]
  4. 返回结果dp[m-1][n-1] 即为所求结果。
完整的规范代码
def uniquePaths(m, n):
    """
    使用动态规划解决不同路径问题
    :param m: int, 网格的行数
    :param n: int, 网格的列数
    :return: int, 不同的路径数量
    """
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]
# 示例调用
print(uniquePaths(3, 7))  # 输出: 28
print(uniquePaths(3, 2))  # 输出: 3
算法分析
  • 时间复杂度:(O(m * n)),需要填充一个 mn 列的矩阵。
  • 空间复杂度:(O(m * n)),使用了一个同样大小的二维数组作为动态规划表。

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

解题步骤
  1. 使用一维数组:利用一维数组 dp 来保存上一行的结果,降低空间复杂度。
  2. 迭代更新:对每一行使用相同的数组进行迭代更新,dp[j] 代表当前行第 j 列的路径数,更新公式仍为 dp[j] = dp[j] + dp[j-1]
  3. 初始化dp 的所有元素初始化为 1。
完整的规范代码
def uniquePaths(m, n):
    """
    使用一维数组进行动态规划
    :param m: int, 网格的行数
    :param n: int, 网格的列数
    :return: int, 不同的路径数量
    """
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[-1]
# 示例调用
print(uniquePaths(3, 7))  # 输出: 28
print(uniquePaths(3, 2))  # 输出: 3
算法分析
  • 时间复杂度:(O(m * n)),需要迭代更新数组 m-1 次,每次迭代有 n-1 步。
  • 空间复杂度:(O(n)),使用了一个长度为 n 的一维数组。

方法三:数学组合方法

解题步骤
  1. 计算组合数:从起点到终点需要走 m+n-2 步,其中 m-1 步向下,n-1 步向右,问题转化为计算从 m+n-2 步中选择 m-1 步的组合数。
  2. 使用公式计算:使用组合数公式 C(k, n) = n! / (k! * (n-k)!) 来计算结果。
完整的规范代码
def uniquePaths(m, n):
    """
    使用数学组合的方法解决不同路径问题
    :param m: int, 网格的行数
    :param n: int, 网格的列数
    :return: int, 不同的路径数量
    """
    from math import factorial
    return factorial(m + n - 2) // (factorial(m - 1) * factorial(n - 1))
# 示例调用
print(uniquePaths(3, 7))  # 输出: 28
print(uniquePaths(3, 2))  # 输出: 3
算法分析
  • 时间复杂度:(O(m + n)),计算阶乘的时间复杂度。
  • 空间复杂度:(O(1)),除输入外不需要额外的存储空间。

方法四:深度优先搜索(DFS)

解题步骤
  1. DFS递归:从起点开始,递归地探索所有向右和向下的路径。
  2. 终止条件:当到达终点时,路径计数增加。
  3. 优化:使用记忆化存储已经计算过的位置的路径数,避免重复计算。
完整的规范代码
def uniquePaths(m, n):
    """
    使用DFS和记忆化搜索解决不同路径问题
    :param m: int, 网格的行数
    :param n: int, 网格的列数
    :return: int, 不同的路径数量
    """
    memo = {}
    def dfs(x, y):
        if (x, y) in memo:
            return memo[(x, y)]
        if x == m - 1 and y == n - 1:
            return 1
        paths = 0
        if x < m - 1:
            paths += dfs(x + 1, y)
        if y < n - 1:
            paths += dfs(x, y + 1)
        memo[(x, y)] = paths
        return paths
    return dfs(0, 0)
# 示例调用
print(uniquePaths(3, 7))  # 输出: 28
print(uniquePaths(3, 2))  # 输出: 3
算法分析
  • 时间复杂度:(O(m * n)),使用记忆化后避免了重复计算。
  • 空间复杂度:(O(m * n)),使用了额外的哈希表来存储中间结果。

方法五:广度优先搜索(BFS)

解题步骤
  1. 队列实现BFS:使用队列存储每个位置和到达该位置的路径数量。
  2. 逐层扩展:从起点开始,逐层扩展到可达的右侧和下侧格子。
  3. 累加路径数:到达终点的路径数累加。
完整的规范代码
from collections import deque
def uniquePaths(m, n):
    """
    使用BFS解决不同路径问题
    :param m: int, 网格的行数
    :param n: int, 网格的列数
    :return: int, 不同的路径数量
    """
    queue = deque([(0, 0)])
    paths = [[0] * n for _ in range(m)]
    paths[0][0] = 1
    while queue:
        x, y = queue.popleft()
        for dx, dy in [(1, 0), (0, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                if paths[nx][ny] == 0:
                    queue.append((nx, ny))
                paths[nx][ny] += paths[x][y]
    return paths[m-1][n-1]
# 示例调用
print(uniquePaths(3, 7))  # 输出: 28
print(uniquePaths(3, 2))  # 输出: 3
算法分析
  • 时间复杂度:(O(m * n)),每个节点入队出队一次。
  • 空间复杂度:(O(m * n)),存储每个位置的路径数及队列的空间需求。

不同算法的优劣势对比

特征 方法一: 动态规划 方法二: 空间优化DP 方法三: 数学组合 方法四: DFS 方法五: BFS
时间复杂度 (O(m * n)) (O(m * n)) (O(m + n)) (O(m * n)) (O(m * n))
空间复杂度 (O(m * n)) (O(n)) (O(1)) (O(m * n)) (O(m * n))
优势 直观,易理解 空间效率高 计算最快,非迭代 灵活,适用于复杂边界 层次清晰,适用于大规模
劣势 空间占用高 优化限于列 对大数处理有限制 时间空间成本高 需要额外存储空间

应用示例

游戏开发中的路径发现

在策略游戏或迷宫游戏中,开发者可以利用这些算法来计算从起点到终点的所有可能路径,为游戏的AI决策提供支持,比如在自动生成的迷宫中计算最优路径或在战略游戏中规划单位的行动路线。这些算法提供了不同的效率和实现复杂度,使得开发者可以根据具体游戏场景和性能要求选择最适合的方法。

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

相关文章
|
12天前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
39 2
|
3天前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
3天前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和
|
3天前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
10天前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
26 6
|
12天前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
22 3
|
12天前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
10 1
|
12天前
|
Python
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
10 1
|
12天前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
11 0
【Leetcode刷题Python】73. 矩阵置零
|
3天前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。