leetcode：62. 不同路径

题目

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

示例：
[中等] 62. 不同路径 - 图1

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

解答 & 代码

解法一：动态规划（二维数组）

动态规划：

  • 动态规划数组 dp：dp[i][j] 代表到达网格 [i, j] 的不同路径数
  • 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    • 最后一步可以是向下走的 or 向右走的，向下走的路径数取决于 dp[i - 1][j]，向右走的路径数取决于 dp[i][j - 1]

  • 初始化：初始将第 0 行和第 0 列所有网格的路径数都设为 1

    1. class Solution {
    2. public:
    3.   int uniquePaths(int m, int n) {
    4.       // 动态规划数组：dp[i][j] 代表到达网格 [i, j] 的不同路径数
    5.       vector<vector<int>> dp(m, vector<int>(n, 0));
    6.       // 初始化
    7.       dp[0][0] = 1;
    8.       for(int j = 1; j < n; ++j)        // 第 0 行
    9.           dp[0][j] = dp[0][j - 1];
    10.       for(int i = 1; i < m; ++i)        // 第 0 列
    11.           dp[i][0] = dp[i - 1][0];
    12.       // 状态转移
    13.       for(int i = 1; i < m; ++i)
    14.       {
    15.           for(int j = 1; j < n; ++j)
    16.               dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    17.       }
    18.       return dp[m - 1][n - 1];
    19.   }
    20. };

    复杂度分析：m x n 网格

  • 时间复杂度 O(m x n)：

  • 空间复杂度 O(m x n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.2 MB, 在所有 C++ 提交中击败了 57.97% 的用户

解法二：动态规划优化（行数组）

由于每个状态 dp[i][j] 只和上方一格状态 dp[i-1][j]、左边一格状态 dp[i][j-1] 有关，所以实际上可以将二维动态规划数组压缩为一维行数组

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         vector<int> dp(n, 1);
  5.         for(int i = 1; i < m; ++i)
  6.         {
  7.             for(int j = 1; j < n; ++j)
  8.                 dp[j] = dp[j] + dp[j - 1];
  9.         }
  10.         return dp[n - 1];
  11.     }
  12. };

复杂度分析：m x n 网格

  • 时间复杂度 O(m x n)：
  • 空间复杂度 O(n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.9 MB, 在所有 C++ 提交中击败了 82.32% 的用户