⭐算法OJ⭐矩阵的干系利用【动态规划 + 组合数学】（C++ 实现）Unique Paths 系列

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

1. Input: m = 3, n = 7
2. Output: 28
4. Input: m = 3, n = 2
5. Output: 3
6. Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
7. 1. Right -> Down -> Down
8. 2. Down -> Down -> Right
9. 3. Down -> Right -> Down

复制代码

动态规划

思绪

• 界说一个二维数组 dp，此中 dp[j] 体现从出发点 (0, 0) 到点 (i, j) 的路径数。
  
• 呆板人只能向右或向下移动，因此状态转移方程为： dp[j] = dp[i - 1][j] + dp[j - 1]
  
• 初始化：第一行和第一列的全部格子只有一种路径（只能不停向右或不停向下），因此 dp[0][j] = 1 和 dp[0] = 1。
  

实当代码

1. int uniquePaths(int m, int n) {
2.     // 定义 dp 数组
3.     vector<vector<int>> dp(m, vector<int>(n, 1));
5.     // 填充 dp 数组
6.     for (int i = 1; i < m; i++) {
7.         for (int j = 1; j < n; j++) {
8.             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
9.         }
10.     }
12.     return dp[m - 1][n - 1];
13. }

复制代码

复杂度分析

• 时间复杂度：O(m * n)，必要添补整个 dp 数组。
  
• 空间复杂度：O(m * n)，必要一个二维数组存储中心结果。
  

组合数学

思绪

• 从出发点 (0, 0) 到尽头 (m - 1, n - 1)，呆板人必要移动 m - 1 次向下和 n - 1 次向右。
  
• 总移动次数为 (m - 1) + (n - 1) = m + n - 2。
  
• 题目转化为从 m + n - 2 次移动中选择 m - 1 次向下（或 n - 1 次向右）的组合数。
  
• 组合数公式为：C(m + n - 2, m - 1) = (m + n - 2)! / ((m - 1)! * (n - 1)!)
  

实当代码

1. int uniquePaths(int m, int n) {
2.     // 计算组合数 C(m + n - 2, m - 1)
3.     long long result = 1;
4.     int total = m + n - 2; // 总移动次数
5.     int k = min(m - 1, n - 1); // 选择较小的值计算组合数
7.     for (int i = 1; i <= k; i++) {
8.         result = result * (total - k + i) / i;
9.     }
11.     return (int)result;
12. }

复制代码

复杂度分析

• 时间复杂度：O(min(m, n))，只必要盘算组合数。
  
• 空间复杂度：O(1)，只利用了常数空间。
  

63. Unique Paths II

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Example 1:

1. Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
2. Output: 2
3. Explanation: There is one obstacle in the middle of the 3x3 grid above.
4. There are two ways to reach the bottom-right corner:
5. 1. Right -> Right -> Down -> Down
6. 2. Down -> Down -> Right -> Right

复制代码

Example 2:

1. Input: obstacleGrid = [[0,1],[0,0]]
2. Output: 1

复制代码

这个题目是带停滞物的呆板人路径题目，可以通过动态规划来办理。我们必要思量停滞物对路径的影响，并在动态规划的过程中跳过停滞物。
动态规划

界说状态

设 dp[j] 体现从出发点 (0, 0) 到点 (i, j) 的路径数。
状态转移方程

• 假如 grid[j] == 1（停滞物），则 dp[j] = 0，由于无法通过停滞物。
  
• 否则，dp[j] = dp[i - 1][j] + dp[j - 1]，即从上方或左方到达当前点的路径数之和。
  

初始化

• 假如出发点 (0, 0) 是停滞物，则直接返回 0，由于无法开始移动。
  
• 初始化第一行和第一列：
  
  
  
  • 假如某个格子是停滞物，则它及厥后续格子的路径数都为 0。
    
  • 否则，路径数为 1（只能不停向右或不停向下）。
    
  
  

1. int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
2.     int m = obstacleGrid.size(), n = obstacleGrid[0].size();
3.     vector<vector<int>> dp(m, vector<int>(n, 0));
4.     dp[0][0] = 1;
5.     for (int i = 1; i < m; i++) {
6.         if (obstacleGrid[i][0] == 1) {
7.             dp[i][0] = 1;
8.         }
9.         else {
10.             dp[i][0] = dp[i - 1][0];
11.         }
12.     }
13.     for (int j = 1; j < n; j++) {
14.         if (obstacleGrid[0][j] == 1) {
15.             dp[0][j] = 0;
16.         }
17.         else {
18.             dp[0][j] = dp[0][j - 1];
19.         }
20.     }
21.     for (int i = 1; i < m; i++) {
22.         for (int j = 1; j < n; j++) {
23.             if (obstacleGrid[i][j] == 1) {
24.                 dp[i][j] = 0;
25.             }
26.             else {
27.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
28.             }  
29.         }
30.     }
31.     return dp[m - 1][n - 1];
32. }

复制代码

复杂度分析

• 时间复杂度：O(m * n)，必要遍历整个网格。
  
• 空间复杂度：O(m * n)，必要一个二维数组存储中心结果。
  

优化空间复杂度

我们可以将空间复杂度优化为 O(n)，由于每次更新 dp[j] 时只必要用到当前行和前一行的数据。
状态转移方程

对于每一行 i，从左到右更新 dp[j]：dp[j] = dp[j] + dp[j - 1]

• dp[j] 体现从上方来的路径数（即上一行的 dp[j]）。
  
• dp[j - 1] 体现从左方来的路径数（即当前行的 dp[j - 1]）。
  

1. int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
2.     int m = obstacleGrid.size();
3.     int n = obstacleGrid[0].size();
4.     if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
5.         return 0;
6.     }
7.     vector<int> dp(n, 0);
8.     dp[0] = 1;
9.     for (int i = 0; i < m; i++) {
10.         for (int j = 0; j < n; j++) {
11.             if (obstacleGrid[i][j] == 1) {
12.                 dp[j] = 0;
13.             } else if (j > 0) {
14.                 dp[j] += dp[j - 1];
15.             }
16.         }
17.     }
18.     return dp[n - 1];
19. }

复制代码