本文共 1138 字，大约阅读时间需要 3 分钟。

根据给定的网格和障碍点，使用动态规划来计算从起点(0,0)到终点(m-1,n-1)的唯一路径数目。这种方法通过记录每个点的路径数来避免重复计算，确保在每一个点只遍历一次。

定义dp[i][j]表示从起点到点(i,j)的路径数目。状态转移方程如下：

• 如果obstacleGrid[i][j] == 1，则dp[i][j] = 0，因为障碍点不能通过。
• 否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]，从上方或左方转移而来。

需要注意边界条件：

• dp[0][0] = 1，起点有唯一路径。
• 第一行和第一列分别只能从起点或同行前面的点转移而来，因此需要单独处理。

以下是优化后的代码：

#include 
   
    using namespace std;class Solution {public:    int uniquePathsWithObstacles(vector
    
     
      > obstacleGrid) {        int m = obstacleGrid.size();        int n = obstacleGrid[0].size();        if (m == 0 || n == 0) return 0;        vector
      
        dp(n);        vector
       
         prev_dp(n);        vector
        
          curr_dp(n); // 初始化第一行 int i = 0; while (i < n && obstacleGrid[0][i] == 0) { dp[i] = 1; i++; } // 初始化第一列 int j = 0; while (j < m && obstacleGrid[j][0] == 0) { dp[j] = 1; j++; } for (i = 1; i < m; i++) { for (j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) dp[j] = 0; else dp[j] = dp[j-1] + curr_dp[j-1]; } } return dp.back(); }};
        
       
      
     
    
   

优化点：

这个方法时间复杂度为O(m*n)，空间复杂度为O(n)，适用于较大的网格。