最近一网友因为入职体检被华为给拒了，工作没了，原因是体检查出 预激综合征，真是麻绳专挑细处断，噩运只找苦命人。 我在网上还特意查了一下，预 激综合征 一般是不会影响入职的，虽然是这样说，但是愿不愿意录用还是招聘方说的算。
来看下今天的算法题，这题是LeetCode的第63题：不同路径 II。
问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次 只能向下或者向右移动一步 。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
输入 ：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出 ：2
解释 ：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
输入 ：obstacleGrid = [[0,1],[0,0]]
输出 ：1
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
动态规划解决
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int dp[][] = new int[m + 1][n + 1]; // 如果起始点有障碍物，则到不了任何位置。 if (obstacleGrid[0][0] == 1) return 0; dp[0][1] = 1;// 如果起始点没有障碍物，到当前位置的路径个数是 1 。 // dp[1][0] = 1;// 或者使用这个也可以 for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (obstacleGrid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m][n];}
public: int uniquePathsWithObstacles(vector<vector<int>> obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> dp(m + 1, vector(n + 1, 0)); // 如果起始点有障碍物，则到不了任何位置。 if (obstacleGrid[0][0] == 1) return 0; dp[0][1] = 1;// 如果起始点没有障碍物，到当前位置的路径个数是 1 。 // dp[1][0] = 1;// 或者使用这个也可以 for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (obstacleGrid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m][n]; }
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] (n + 1) for _ in range(m + 1)] # 如果起始点有障碍物，则到不了任何位置。 if obstacleGrid[0][0]: return 0 dp[0][1] = 1 # 如果起始点没有障碍物，到当前位置的路径个数是 1 。 # dp[1][0] = 1 # 或者使用这个也可以 for i in range(1, m + 1): for j in range(1, n + 1): if not obstacleGrid[i - 1][j - 1]: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m][n]
