Unique Paths

62. 不同路径

分析

状态定义：
- 用 f[i][j] 表示从起点 (0, 0) 到达网格位置 (i, j) 的不同路径数
状态转移：
- 如果机器人能够从上方或左方到达 (i, j)：
  - 从上方到达：路径数为 f[i-1][j]
  - 从左方到达：路径数为 f[i][j-1]
- 因此，状态转移方程为：f[i][j] = f[i-1][j] + f[i][j-1]
初始条件：
- 起点 (0, 0) 的路径数为 1，即 f[0][0] = 1
- 第一行和第一列的位置只能从一个方向到达：
  - 第一行：只能从左到右
  - 第一列：只能从上到下

时间复杂度

需要遍历整个网格，时间复杂度为 O(mn)

空间复杂度

空间复杂度为 O(mn)

C++代码

 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


class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        // 创建一个二维数组 f，用于记录每个位置的路径数
        std::vector<std::vector<int>> f(n, std::vector<int>(m));

        // 遍历每个位置
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                // 初始化起点
                if (i == 0 && j == 0)
                    f[i][j] = 1;
                else
                {
                    // 从上方到达
                    if (i)
                        f[i][j] += f[i - 1][j];
                    // 从左方到达
                    if (j)
                        f[i][j] += f[i][j - 1];
                }
            }
        }
        // 返回终点的路径数
        return f[n - 1][m - 1];
    }
};