代码随想录算法训练营第三十九天 | 力扣 62.不同路径, 63. 不同路径 II

62.不同路径

题目

62. 不同路径

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

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

问总共有多少条不同的路径?

解析

1.确定dp数组(dp table)以及下标的含义

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

2.确定递推公式

想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。

此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

3.dp数组的初始化

首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

所以初始化代码为:

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

4.确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

5.举例推导dp数组

如图所示:

Java代码实现

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        }
    }
    return dp[m - 1][n - 1];
}

63. 不同路径 II

题目

63. 不同路径 II

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

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

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

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

解析

1.确定dp数组(dp table)以及下标的含义

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

2.确定递推公式

递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

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

所以代码为:

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

3.dp数组如何初始化 

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

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

4.确定遍历顺序

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

5.举例推导dp数组

Java代码实现

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
        dp[0][i] = 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];
        }
    }
    return dp[m - 1][n - 1];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/24115.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++数据结构:二叉树之一(数组存储)

文章目录 前言一、二叉树的基本定义二、二叉树的基本性质三、二叉树的存储&#xff08;数组&#xff09;总结原创文章&#xff0c;未经许可&#xff0c;禁止转载 前言 树是一种非线性数据结构&#xff0c;它由若干个节点和边组成。每个节点都有一个值&#xff0c;而边则表示节…

day17 - 用形状包围图像

在进行图像轮廓提取时&#xff0c;有的情况下不需要我们提取出精确的轮廓&#xff0c;只要提取出一个接近于轮廓的近似多边形&#xff0c;就可以满足后续的操作。 本期我们来学习如何通过设置参数来找出图像的近似多边形。 完成本期内容&#xff0c;你可以&#xff1a; 了解…

算法基础学习笔记——⑨C++STL使用技巧

✨博主&#xff1a;命运之光 ✨专栏&#xff1a;算法基础学习 目录 ✨CSTL简介 ✨CSTL使用技巧 前言&#xff1a;算法学习笔记记录日常分享&#xff0c;需要的看哈O(∩_∩)O&#xff0c;感谢大家的支持&#xff01; ✨CSTL简介 vector变长数组&#xff0c;倍增的思想//系统为…

STM32单片机(三)第一节:GPIO输出

❤️ 专栏简介&#xff1a;本专栏记录了从零学习单片机的过程&#xff0c;其中包括51单片机和STM32单片机两部分&#xff1b;建议先学习51单片机&#xff0c;其是STM32等高级单片机的基础&#xff1b;这样再学习STM32时才能融会贯通。 ☀️ 专栏适用人群 &#xff1a;适用于想要…

驱动开发:内核读写内存浮点数

如前所述&#xff0c;在前几章内容中笔者简单介绍了内存读写的基本实现方式&#xff0c;这其中包括了CR3切换读写&#xff0c;MDL映射读写&#xff0c;内存拷贝读写&#xff0c;本章将在如前所述的读写函数进一步封装&#xff0c;并以此来实现驱动读写内存浮点数的目的。内存浮…

MyBatis操作数据库表和动态SQL的使用

目录 1.MyBatis开发环境的搭建和测试 2.MyBatis基本操作 2.0 准备工作 2.1 新增操作 2.2 删除、修改、查询操作 2.3 #{param} 和 ${param}的使用和区别 2.4 实体对象属性和数据库字段名称不同时如何映射&#xff1f; 3. MyBatis多表查询 3.0 准备工作 3.1 一对一的表…

ELK企业级日志分析系统

ELK概述 为什么要使用 ELK 日志主要包括系统日志、应用程序日志和安全日志。系统运维和开发人员可以通过日志了解服务器软硬件信息、检查配置过程中的错误及错误发生的原因。经常分析日志可以了解服务器的负荷&#xff0c;性能安全性&#xff0c;从而及时采取措施纠正错误。 往…

切比雪夫不等式,大数定律及极限定理。

一.切比雪夫不等式 1.定理 若随机变量X的期望EX和方差DX存在,则对任意ε > 0,有   P{ |X - EX| > ε } < DX/ε2 或 P{ |X - EX| < ε } > 1 - DX/ε2 2.解析定理 ①该定理对 X 服从什么分布不做要求&#xff0c;仅EX DX存在即可。 ②“| |” 由于X某次…

软件测试炸了,作为从业者,你做好准备了吗?

软件测试行业已经发生很大变化&#xff0c;你跟上变化了吗&#xff1f; 岗位少不可怕&#xff0c;要求越来越高也不可怕&#xff0c;可怕的是&#xff0c;软件测试行业已经发生巨变&#xff0c;而你却原地踏步&#xff01;目前一线大厂更多倾向于招收测试开发&#xff0c;或者…

自学网络安全(黑客),一般人我劝你还是算了吧

一、自学网络安全学习的误区和陷阱 1.不要试图先成为一名程序员&#xff08;以编程为基础的学习&#xff09;再开始学习 我在之前的回答中&#xff0c;我都一再强调不要以编程为基础再开始学习网络安全&#xff0c;一般来说&#xff0c;学习编程不但学习周期长&#xff0c;而且…

torch.distributed.launch多卡多机

torch.distributed.launch命令介绍 我们在训练分布式时候&#xff0c;会使用到 torch.distributed.launch 可以通过命令&#xff0c;来打印该模块提供的可选参数 python -m torch.distributed.launch --help usage: launch.py [-h] [--nnodes NNODES] [--node_rank NODE_RANK]…

诚迈科技携智达诚远出席高通汽车技术与合作峰会

5月25日至26日&#xff0c;诚迈科技及旗下的智能汽车操作系统及中间件产品提供商智达诚远作为高通生态伙伴&#xff0c;亮相首届“高通汽车技术与合作峰会”&#xff0c;通过产品展示和主题演讲呈现了基于高通骁龙数字底盘的最新智能座舱技术成果&#xff0c;共同展望智能网联汽…

GcExcel v6.1 支持新的 ‘.sjs‘ 模板文件 ‘.xltx‘ 格式 Crack

GrapeCity Documents for Excel (GcExcel) v6.1 版本现已上线&#xff01;该版本支持新的 SpreadJS .sjs 文件格式和 Excel 模板文件 .xltx 格式。此外&#xff0c;GcExcel 支持更多的SpreadJS兼容性功能和对 GcDataViewer 的多项增强。看看下面的主要亮点。 导入/导出 Spread…

Revit幕墙:用幕墙巧做屋面瓦及如何快速幕墙?

一、Revit中用幕墙巧做屋面瓦 屋面瓦重复性很高&#xff0c;我们如何快速的创建呢?下面我们来学会快速用幕墙来创建屋面瓦的技巧。 1.新建“公制轮廓-竖挺”族&#xff0c;以此来创建瓦的族(以便于载入项目中使用) 2.在轮廓族中绘制瓦的轮廓(轮廓需要闭合)&#xff0c;将族名称…

【JavaSE】Java基础语法(三十四):实现多线程

文章目录 1. 简单了解多线程2. 并发和并行3. 进程和线程4. 实现多线程方式一&#xff1a;继承Thread类【应用】5. 实现多线程方式二&#xff1a;实现Runnable接口【应用】6. 实现多线程方式三: 实现Callable接口【应用】7. 设置和获取线程名称【应用】8. 线程休眠【应用】9. 线…

Z-Library2023现状

网上基本上年年都会传出来Z-Library要被干掉的消息&#xff0c;我一直觉得&#xff0c;如果那真的发生了&#xff0c;会是人类的悲哀。 由于之前我存储的地址又挂了&#xff0c;所以紧急又寻找了一下。 1.朋友帮忙 朋友帮我搜了一下&#xff0c;发现有三个地址。 他说这第一个…

xlsx是什么格式

xlsx是什么格式? xlsx是Excel文档的扩展名&#xff0c;其基于Office Open XML标准的压缩文件格式&#xff0c;取代了其以前专有的默认文件格式&#xff0c;在传统的文件名扩展名后面添加了字母x&#xff0c;即.xlsx取代.xls。 xlsx文件是什么格式? xlsx是Excel表格的文件格…

【P34】JMeter ForEach控制器(ForEach Controller)

文章目录 一、ForEach控制器&#xff08;ForEach Controller&#xff09;参数说明二、准备工作三、测试计划设计 一、ForEach控制器&#xff08;ForEach Controller&#xff09;参数说明 可以对一个组变量进行循环迭代&#xff1b;该组件通常与后置处理器中的 JSON 提取器、正…

桥梁结构健康监测解决方案

城市桥梁担负着城市的交通和运输网络的重要角色&#xff0c;是城市生命线的重要组成部分。然而&#xff0c;随着时间的推移和日益增长的负荷&#xff0c;桥梁可能会受到各种因素的损害&#xff0c;如自然灾害、疲劳、腐蚀等。因此&#xff0c;桥梁结构健康监测变得至关重要&…

chatgpt赋能Python-python中怎么导入numpy

介绍 Python是一种广泛使用的编程语言&#xff0c;具有许多内建功能和模块&#xff0c;让开发者能够快速地编写代码。然而&#xff0c;虽然能够实现许多计算&#xff0c;但是原始Python本身并不足够处理各种科学和数字计算上需要的高效性&#xff0c;因此numpy这个开源的Pytho…