05_不同路径2(带障碍物版)

简介: 05_不同路径2(带障碍物版)

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 10 来表示。

【思路】

动规五部曲:

1、确定dp数组以及下标的含义

dp[i][j]:表示从(0,0)出发,到(i,j)有dp[i][j]条不同的路径。

2、确定递推公式

递推公式和上面那题一样,dp[i][j] = dp[i-1][j]+dp[i][j-1]。

但这里需要注意的是,因为有了障碍的话应该就保持初始状态(初始状态为0)。

if (obstacleGrid[i][j] == 0) {//当(i, j)没有障碍的时候,再推导dp[i][j]
  dp[i][j] = dp[i-1][j] + dp[i][j-1];
}

3、dp数组如何初始化

int[][] dp = new int[m][n];
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

因为从(0,0)的位置到(i,0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。

但如果(i, 0)这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。

注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理

4、确定遍历顺序

从递归公式dp[i][j]=dp[i-1][j]+dp[i][j-1]中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]的时候,dp[i-1][j]和dp[i][j-1]一定有数值。

for(int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    if(obstacleGrid[i][j] == 1) continue;
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}

5、举例推导dp数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //如果在起点或终点出现了障碍,直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}
相关文章
|
存储 数据库
工作流Flowable 数据库表结构说明、Flowable 数据字典说明
工作流Flowable 数据库表结构说明、Flowable 数据字典说明
1763 0
|
监控 Java API
掌握 Spring Boot AOP:使用教程
Spring Boot 中的面向切面编程(AOP)为软件开发提供了一种创新方法,允许开发者将横切关注点与业务逻辑相分离。这不仅提高了代码的复用性和可维护性,而且还降低了程序内部组件之间的耦合度。下面,我们深入探讨如何在 Spring Boot 应用程序中实践 AOP,以及它为项目带来的种种益处。
|
Java 关系型数据库 MySQL
创建一个SpringBoot项目,实现简单的CRUD功能和分页查询
【9月更文挑战第6天】该内容介绍如何使用 Spring Boot 实现具备 CRUD 功能及分页查询的项目。首先通过 Spring Initializr 创建项目并选择所需依赖;其次配置数据库连接,并创建实体类与数据访问层;接着构建服务层处理业务逻辑;最后创建控制器处理 HTTP 请求。分页查询可通过添加 URL 参数实现。
343 7
|
NoSQL Java 应用服务中间件
大厂面试必备:如何轻松实现分布式Session管理?
这篇文章介绍三种分布式Session的实现方案:基于JWT的Token、基于Tomcat的Redis和基于Spring的Redis。JWT方案通过生成Token存储用户信息,实现无状态、可扩展的会话管理,但可能增加请求负载且数据安全性较低。Tomcat与Redis结合,通过配置Tomcat和Redis,实现Session集中管理和高性能存储,但配置相对复杂。Spring整合Redis适用于SpringBoot和SpringCloud项目,集成方便,扩展性强,但同样依赖外部Redis服务。每种方法有其优缺点,适用场景不同。作者小米是一个技术爱好者,欢迎关注其微信公众号“软件求生”获取更多技术内容
671 4
|
算法 NoSQL Java
springboot整合redis及lua脚本实现接口限流
springboot整合redis及lua脚本实现接口限流
475 0
|
12月前
|
Java
Java面试题之cpu占用率100%,进行定位和解决
这篇文章介绍了如何定位和解决Java服务中CPU占用率过高的问题,包括使用top命令找到高CPU占用的进程和线程,以及使用jstack工具获取堆栈信息来确定问题代码位置的步骤。
764 0
Java面试题之cpu占用率100%,进行定位和解决
|
关系型数据库 MySQL
【MySQL】经典练习题(部门表、员工表、工资表)
【MySQL】经典练习题(部门表、员工表、工资表)
620 0
|
SQL JSON Java
springboot 如何编写增删改查后端接口,小白极速入门,附完整代码
本文为Spring Boot增删改查接口的小白入门教程,介绍了项目的构建、配置YML文件、代码编写(包括实体类、Mapper接口、Mapper.xml、Service和Controller)以及使用Postman进行接口测试的方法。同时提供了SQL代码和完整代码的下载链接。
springboot 如何编写增删改查后端接口,小白极速入门,附完整代码
|
SQL Java 数据库连接
Dao层和Mapper层
Dao层和Mapper层
1701 0
|
存储 物联网 数据库
InfluxDB数据模型与数据结构设计详解
【4月更文挑战第30天】InfluxDB是一款高性能时序数据库,其数据模型由数据库、测量值、标签和字段组成。数据库存储相关数据,测量值类似表格,包含标签和字段。标签是元数据,用于分类和查询优化;字段存储实际数据值。设计时应注意明确测量值、合理定义标签、精简字段,利用标签索引优化查询,以及考虑数据生命周期和保留策略。理解这些概念有助于高效使用InfluxDB处理时序数据。