华为因入职体检被刷，工作没了。。

最近一网友因为入职体检被华为给拒了，工作没了，原因是体检查出预激综合征，真是麻绳专挑细处断，噩运只找苦命人。我在网上还特意查了一下，预激综合征一般是不会影响入职的，虽然是这样说，但是愿不愿意录用还是招聘方说的算。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第63题：不同路径 II。

问题描述

来源：LeetCode第63题

难度：中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

示例1：

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

示例2：

输入：obstacleGrid = [[0,1],[0,0]] 输出：1

• m == obstacleGrid.length

• n == obstacleGrid[i].length

• 1 <= m, n <= 100

• obstacleGrid[i][j] 为 0 或 1

动态规划解决

这题让计算从左上角到右下角有多少个不同的路径，我们昨天讲过和这类似的 ，不过昨天的那道题是没有障碍物的，而这题有障碍物，但我们依然可以使用动态规划来解决这道题。

定义 dp[i][j]表示从左上角走到位置[i,j]不同路径的个数 ，因为只能往下走或往右走，所以要走到位置[i,j]可以从上面下来，也就是dp[i-1][j]，或者从左边过来，也就是dp[i][j-1]，所以总的路径个数就是dp[i-1][j]+dp[i][j-1]，但这里要注意下，如果有障碍物的话是不能走的。

因为第一行上边是没有数据的，第一列左边也是没有数据的，所以为了减少一些边界条件的判断，可以让dp的宽和高增加 1 ，来看下代码。

JAVA：

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];
}

C++：

public:
    int uniquePathsWithObstacles(vector

 > &obstacleGrid) {         int m = obstacleGrid.size();         int n = obstacleGrid[0].size();         vector

 > 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];     }

Python：

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]

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。