Q63 Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

Note: m and n will be at most 100.

Example 1:
Input: [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
解题思路:

这个题就不能像 Q62 Unique Paths 使用数学技巧求解了。但是我们同样可以使用动态规划,只不过有障碍物的地方 dp[i][j] 的值为 0 即可。

具体做法:刚开始初始化 dp[n][m] 时都要初始化为 0(因为可能有障碍)。对于第一行和第一列单独计算,第一行从左到右(或第一列从上到下)如果没有障碍,初始化为 1;有障碍,第一行(或第一列)后面的都要是 0 (因为后面的路不通)。在计算中间结点时,如果有障碍,dp[i][j] 的值也是0;没有障碍就更新 dp[i][j] 的值:dp[i][j] = dp[i][j-1] + dp[i-1][j]

Python 实现:
class Solution:
    # DP
    # Time: O(n^2)
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        if obstacleGrid[row-1][col-1] == 1:
            return 0
        dp = [[0 for _ in range(col)] for _ in range(row)]
        for i in range(row):  # 初始化第一行,遇到阻碍后面都是0
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1 
            else:
                break
        for j in range(col):  # 初始化第一列,遇到阻碍后面都是0
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
        for i in range(1, row):
            for j in range(1, col):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[i][j]

obstacleGrid1 = [[0,1,0],[0,1,0],[0,0,0]]
obstacleGrid2 = [[0,0,0],[0,1,0],[0,0,0]]
print(Solution().uniquePathsWithObstacles(obstacleGrid1))  # 1
print(Solution().uniquePathsWithObstacles(obstacleGrid2))  # 2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Fish

CCF 最优灌溉

问题描述   雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉。   为了灌溉,雷雷需要建立一些...

23470
来自专栏决胜机器学习

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(十)——有向无环图与拓扑算法 (原创内容,转载请注明来源,谢谢) 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。...

612110
来自专栏mathor

枚举+优化(5)——双指针优化1

15930
来自专栏进击的程序猿

seq2seq模型之raw_rnn

本文是seq2seq模型的第二篇,主要是通过raw_rnn来实现seq2seq模型。 github地址是:https://github.com/zhuanxu...

35220
来自专栏chenjx85的技术专栏

leetcode-201-数字范围按位与

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

49220
来自专栏机器学习之旅

tf.nn.embedding_lookup记录

我觉得这张图就够了,实际上tf.nn.embedding_lookup的作用就是找到要寻找的embedding data中的对应的行下的vector。

17220
来自专栏数据结构与算法

洛谷P3388 【模板】割点(割顶)(tarjan求割点)

题目背景 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点。 输入输出格式 输入格式: 第一行输入n,m 下面m行每行输入x,y表示x到y有一条边 ...

39460
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

12920
来自专栏Java架构沉思录

什么是一致性哈希算法

原文:http://www.cnblogs.com/hapjin/p/4737207.html

17410
来自专栏云时之间

小白笔记——R语言(1)

最近一段时间的R语言学习笔记,以便于自己学习之用,特记录在博客中,感兴趣的人还可以看看。记录的东西也不一定正确,请大家指教,里面可能会引用到一些别人的资料等,作...

35690

扫码关注云+社区

领取腾讯云代金券