LintCode 不同的路径 II 题目分析代码

题目

"不同的路径" 的跟进问题: 现在考虑网格中有障碍物,那样将会有多少条不同的路径? 网格中的障碍和空位置分别用 1 和 0 来表示。

** 注意事项 m 和 n 均不超过100 **

样例 如下所示在3x3的网格中有一个障碍物:

diffRoute2.PNG

一共有2条不同的路径从左上角到右下角。

分析

依然和前述的不同路径问题一样,就是增加了障碍点,遇到障碍点我们就跳过即可。

代码

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        int[][] dp = new int[100][100];  
        int r=obstacleGrid.length;  
        int c=obstacleGrid[0].length;  
  
        for(int i=0;i<r;++i){  //第一列  
            if(0==obstacleGrid[i][0])  //因为只能向下或者向右走,所以从起点来到该点方法有一种  
                dp[i][0]=1;  
            else  
                break;         //阻塞了,接下来不用考虑下面的点,肯定走不到  
        }     
        for(int i=0;i<c;++i){ //第一行 同理  
            if(0==obstacleGrid[0][i])  
                dp[0][i]=1;  
            else  
                break;  
        }     
        for(int i=1;i<r;++i)  
            for(int j=1;j<c;++j){  
                if(0==obstacleGrid[i][j])  
                    dp[i][j]=dp[i-1][j]+dp[i][j-1]; //从起点走到该点有几种途径等于  
                                                    //从起点到该点上面的点和该点左  
                                                    //边的点途径之和  
                else                                  
                    dp[i][j]=0;  
            }  
        return dp[r-1][c-1];  
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏linux驱动个人学习

Linux CFS调度器之负荷权重load_weight--Linux进程的管理与调度(二十五)

负荷权重用struct load_weight数据结构来表示, 保存着进程权重值weight。其定义在/include/linux/sched.h, v=4.6...

1281
来自专栏韩东吉的Unity杂货铺

零基础入门 36:代码控制预设

上一篇分享给大家带来了如何通过菜单栏呼出一个自定义的窗口,不知道大家消化的如何了呢?

1144
来自专栏Echo is learning

arcpy 常用操作

1732
来自专栏weixuqin 的专栏

《C++ Primer》学习笔记:迭代器介绍

《C++Primer》(第五版)中,3.4.1的例题中使用一个名为text的字符串向量存放文本文件中的数据,输出text中的内容,刚开始我这样写: #inclu...

3505
来自专栏linux驱动个人学习

分支预测

分支预测( Branch predictor):当处理一个分支指令时,有可能会产生跳转,从而打断流水线指令的处理,因为处理器无法确定该指令的下一条指令,直到分支...

1081
来自专栏XAI

【定制化图像开放平台】入门实例之手写数字模型训练

本帖主要用手写数字为例进行一个简单入门实例总结(非官方) 平台网站:http://ai.baidu.com/customize/app/model/ 定制化图像...

42416
来自专栏Jerry的SAP技术分享

用代码判断当前系统是否支持某个版本的feature

JDK9已经出来有一段时间了,因此很多流行的Java应用纷纷增添了对JDK9乃至JDK10的支持,比如Tomcat。

1392
来自专栏码云1024

matplotlib简介

Matplotlib 是一个 Python 的 2D绘图库,它以各种硬拷贝格式和跨平台的交互式环境生成出版质量级别的图形

4437
来自专栏java初学

一致性哈希算法(consistent hashing)

53614
来自专栏CNN

TensorFlow读取数据

本文介绍如何使用TensorFlow来读取图片数据,主要介绍写入TFRecord文件再读取和直接使用队列来读取两种方式。假设我们图片目录结构如下:

1382

扫码关注云+社区

领取腾讯云代金券