【华为OD技术面试手撕真题】50、不同路径 | 手撕真题+思路参考+代码解析（C & C++ & Java & Python & JS）

在华为的OD技术面试中，算法题目是考核考生综合能力的重要手段之一。其中，“不同路径”问题是一个经典的动态规划题目，涉及到网格的遍历与路径计数。

问题描述

给定一个 m x n 的网格，机器人从左上角 (0, 0) 开始，通过向右或向下移动来达到右下角 (m-1, n-1)。请计算机器人到达目的地的不同路径的数量。

例如，一个 3 x 2 的网格可视化如下：

[
  [0, 0],
  [0, 0],
  [0, 0]
]

从左上角到右下角的不同路径为 3 种，分别是： 1. 右 -> 右 -> 下 -> 下 2. 右 -> 下 -> 右 -> 下 3. 下 -> 右 -> 右 -> 下

思路分析

这个问题可以使用动态规划来解决。我们可以用一个二维数组 dp 来存储到达每个点所需的不同路径数。

动态规划状态转移方程

1. 如果在第 i 行和第 j 列，dp[i][j] 的值是 dp[i-1][j]（从上方到达）和 dp[i][j-1]（从左方到达）的和：

[ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]

1. 边界条件：
2. 第一行的所有位置只能通过左侧的单一路径到达: [ dp[0][j] = 1 \quad (0 \leq j < n) ]
3. 第一列的所有位置只能通过上方的单一路径到达: [ dp[i][0] = 1 \quad (0 \leq i < m) ]

代码示例

以下是该问题的 Python 实现：

def uniquePaths(m, n):
    # 创建一个 m x n 的 DP 数组
    dp = [[0] * n for _ in range(m)]

    # 初始化第一行和第一列
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    # 填充 DP 数组
    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]

# 调用函数，计算 3x2 网格的不同路径
print(uniquePaths(3, 2))  # 输出: 3

代码解析

1. 初始化：

2. 创建一个二维数组 dp，并初始化第一行和第一列的值为 1，因为到达这些位置只有一种路径。

3. 状态转移：

4. 使用两重循环遍历网格中的每个位置（从 (1, 1) 开始），根据状态转移方程填充 dp 数组。

5. 返回结果：

6. 最终，dp[m-1][n-1] 就是从起点到终点的不同路径数量。

复杂度分析

• 时间复杂度：O(m * n)，需要遍历所有的格子。
• 空间复杂度：O(m * n)，需要额外的 DP 数组存储路径数量。

总结

“不同路径”问题是一个基础但极具代表性的动态规划例题，清晰的思路和良好的编码习惯对成功解决问题至关重要。在面试中，理解问题、设计状态转移并实现代码的能力都是考察的重点。希望这篇文章能帮助到正在准备面试的你。