LeetCode题解:63. 不同路径 II,动态规划,JavaScript,详细注释

2024-06-14 07:04

本文主要是介绍LeetCode题解:63. 不同路径 II,动态规划,JavaScript,详细注释,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接:https://leetcode-cn.com/problems/unique-paths-ii/

解题思路:

  1. 在网格中的任意一点,都有向右和向下两种走法。同时它也是从上方和左方两个位置走过来的。
  2. 那么,任意一点的走法数量,等于从起点走到上方和左方点的数量之和。
  3. 第一行和第一列都只有一种走法,就是从起点一直走到底。
  4. 我们可以用一个二维数组,画出网格中每个点的走法数量,一直递推到终点,终点存储的就是所有的走法数量。
  5. 因此动态规划的状态转移方程为:dp[i][j]=dp[i-1][j]+dp[i][j-1]
  6. 如果遇到障碍物,则该位置的走法数量为0。
  7. 对于第一行和第一列来说,遇到障碍物之后,从障碍物起,之后的所有位置路径都为0。
/*** @param {number[][]} obstacleGrid* @return {number}*/
var uniquePathsWithObstacles = function(obstacleGrid) {const m = obstacleGrid.length // 缓存行数const n = obstacleGrid[0].length // 缓存列数// 如果起点和终点有障碍物,则没有路径,返回0if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) {return 0}// 创建m行n列数组缓存结果let dp = Array.from({ length: m }, () => new Array(n).fill(0))let canGoDown = true // 用于判断第一列是否可以继续向下走let canGoRight = true // 用于判断第一行是否可以继续向下走// 初始化第一列,如果遇到障碍物,表示从障碍物开始,不可以继续往下走,路径都为0for (let i = 0; i < m; i++) {if (obstacleGrid[i][0]) {canGoDown = false}if (canGoDown) {dp[i][0] = 1}}// 初始化第一行,如果遇到障碍物,表示从障碍物开始,不可以继续往下走,路径都为0for (let i = 0; i < n; i++) {if (obstacleGrid[0][i]) {canGoRight = false}if (canGoRight) {dp[0][i] = 1}}// 从第二行第二列开始完成递推,遇到障碍物的位置,路径为0for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {if (!obstacleGrid[i][j]) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}}// 网格的最后一位为结果return dp[m - 1][n - 1]
};

这篇关于LeetCode题解:63. 不同路径 II,动态规划,JavaScript,详细注释的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059704

相关文章

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J

JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

《JAVA系统中SpringBoot应用程序的配置文件application.yml使用详解》:本文主要介绍JAVA系统中SpringBoot应用程序的配置文件application.yml的... 目录文件路径文件内容解释1. Server 配置2. Spring 配置3. Logging 配置4. Ma

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.

Spring MVC如何设置响应

《SpringMVC如何设置响应》本文介绍了如何在Spring框架中设置响应,并通过不同的注解返回静态页面、HTML片段和JSON数据,此外,还讲解了如何设置响应的状态码和Header... 目录1. 返回静态页面1.1 Spring 默认扫描路径1.2 @RestController2. 返回 html2

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》:本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时,我们会提供了一个 API 接口去

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、

SpringBoot 整合 Grizzly的过程

《SpringBoot整合Grizzly的过程》Grizzly是一个高性能的、异步的、非阻塞的HTTP服务器框架,它可以与SpringBoot一起提供比传统的Tomcat或Jet... 目录为什么选择 Grizzly?Spring Boot + Grizzly 整合的优势添加依赖自定义 Grizzly 作为

Java后端接口中提取请求头中的Cookie和Token的方法

《Java后端接口中提取请求头中的Cookie和Token的方法》在现代Web开发中,HTTP请求头(Header)是客户端与服务器之间传递信息的重要方式之一,本文将详细介绍如何在Java后端(以Sp... 目录引言1. 背景1.1 什么是 HTTP 请求头?1.2 为什么需要提取请求头?2. 使用 Spr