vlambda博客
学习文章列表

本节为动态规划第六题：不同路径II(unique-paths-ii)，主要包括：问题描述，算法思路，复杂度分析，C++实现。

1. 问题描述

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

  网格中障碍物和空位置用1，0表示，m和n的值均不超过100。

示例：
  输入:
  [
   [0,0,0],
   [0,1,0],
   [0,0,0]
  ]
  输出: 2
  解释:
  3x3 网格的正中间有一个障碍物。
  从左上角到右下角一共有 2 条不同的路径：
  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

2. 动态规划解法

  根据没有障碍物的版本的问题，我们知道状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]。
  有障碍物的版本中需要额外的一些工作，算法思路如下：

• 若第一个点dp[0][0]为1，则说明有障碍物，那么机器人不能做任何移动，返回0；

• 如果dp[0][0]为0，没有障碍物，初始化这个值为1；

• 遍历第一行，如果一个点初始值为1，说明有障碍物，没有路径可以通过，设值为0；否则dp[i,j]=dp[i,j-1]

• 同样遍历第一列，初始值不为1则dp[i][j]=dp[i-1][j]

• 从dp[1[[1]开始遍历数组，如果某个点初始无障碍，则dp[i][j]=dp[i-1][j]+dp[i][j-1]；否则这个点设为0，保证不会对后面的路径有贡献。

  因为我们可以利用输入矩阵作为dp数组，所以空间复杂度O(1)，时间复杂度O(m*n)。

//1.动态规划，时间复杂度O(m*n)，空间复杂度O(1) int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int row_num = obstacleGrid.size(); int col_num = obstacleGrid[0].size(); if (obstacleGrid[0][0] == 1) return 0; obstacleGrid[0][0] = 1; for (int i = 1; i < row_num; i++) obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0; for (int j = 1; j < col_num; j++) obstacleGrid[0][j] = (obstacleGrid[0][j] == 0 && obstacleGrid[0][j - 1] == 1) ? 1 : 0; for (int i = 1; i < row_num; i++) { for (int j = 1; j < col_num; j++) { if (obstacleGrid[i][j] == 0) obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; else obstacleGrid[i][j] = 0; } } return obstacleGrid[row_num - 1][col_num - 1]; }