当前位置: 首页 > news >正文

代码随想录算法训练营第23期day39 |62.不同路径、63. 不同路径 II

目录

一、(leetcode 62)不同路径

1.动态规划

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

2)确定递推公式

3)dp数组的初始化

4)确定遍历顺序

5)举例推导dp数组

 2.数论方法

二、(leetcode 63)不同路径 II


一、(leetcode 62)不同路径

力扣题目链接

1.动态规划

机器人从(0 , 0) 位置出发,到(m - 1, n - 1)终点。

按照动规五部曲来分析:

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数组

如图所示:

62.不同路径1

以上动规五部曲分析完毕,C++代码如下:

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 1;for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
  • 时间复杂度:O(m × n)
  • 空间复杂度:O(m × n)

其实用一个一维数组(也可以理解是滚动数组)就可以了,但是不利于理解,可以优化点空间,建议先理解了二维,在理解一维,C++代码如下:

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for (int i = 0; i < n; i++) dp[i] = 1;for (int j = 1; j < m; j++) {for (int i = 1; i < n; i++) {dp[i] += dp[i - 1];}}return dp[n - 1];}
};
  • 时间复杂度:O(m × n)
  • 空间复杂度:O(n)

 2.数论方法

在这个图中,可以看出一共m,n的话,无论怎么走,走到终点都需要 m + n - 2 步。

62.不同路径

在这m + n - 2 步中,一定有 m - 1 步是要向下走的,不用管什么时候向下走。

那么有几种走法呢? 可以转化为,给你m + n - 2个不同的数,随便取m - 1个数,有几种取法。

那么这就是一个组合问题了。

62.不同路径2

求组合的时候,要防止两个int相乘溢出! 所以不能把算式的分子都算出来,分母都算出来再做除法。

例如如下代码是不行的。

class Solution {
public:int uniquePaths(int m, int n) {int numerator = 1, denominator = 1;int count = m - 1;int t = m + n - 2;while (count--) numerator *= (t--); // 计算分子,此时分子就会溢出for (int i = 1; i <= m - 1; i++) denominator *= i; // 计算分母return numerator / denominator;}
};

需要在计算分子的时候,不断除以分母,代码如下:

class Solution {
public:int uniquePaths(int m, int n) {long long numerator = 1; // 分子int denominator = m - 1; // 分母int count = m - 1;int t = m + n - 2;while (count--) {numerator *= (t--);while (denominator != 0 && numerator % denominator == 0) {numerator /= denominator;denominator--;}}return numerator;}
};
  • 时间复杂度:O(m)
  • 空间复杂度:O(1)

二、(leetcode 63)不同路径 II

力扣题目链接

有障碍的话,其实就是标记对应的dp table(dp数组)保持初始值(0)就可以了

动规五部曲:

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

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

2)确定递推公式

递推公式和62.不同路径一样,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数组如何初始化

在62.不同路径 (opens new window)不同路径中我们给出如下的初始化:

vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始值为0
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

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

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

如图:

63.不同路径II

下标(0, j)的初始化情况同理。

所以本题初始化代码为:

vector<vector<int>> dp(m, vector<int>(n, 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循环的终止条件,一旦遇到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数组

拿示例1来举例如题:

63.不同路径II1

对应的dp table 如图:

63.不同路径II2

如果这个图看不懂,建议再理解一下递归公式,然后照着文章中说的遍历顺序,自己推导一下!

动规五部分分析完毕,对应C++代码如下:

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍,直接返回0return 0;vector<vector<int>> dp(m, vector<int>(n, 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++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
  • 时间复杂度:O(n × m),n、m 分别为obstacleGrid 长度和宽度
  • 空间复杂度:O(n × m)

同样给出空间优化版本:

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if (obstacleGrid[0][0] == 1)return 0;vector<int> dp(obstacleGrid[0].size());for (int j = 0; j < dp.size(); ++j)if (obstacleGrid[0][j] == 1)dp[j] = 0;else if (j == 0)dp[j] = 1;elsedp[j] = dp[j-1];for (int i = 1; i < obstacleGrid.size(); ++i)for (int j = 0; j < dp.size(); ++j){if (obstacleGrid[i][j] == 1)dp[j] = 0;else if (j != 0)dp[j] = dp[j] + dp[j-1];}return dp.back();}
};
  • 时间复杂度:O(n × m),n、m 分别为obstacleGrid 长度和宽度
  • 空间复杂度:O(m)

相关文章:

代码随想录算法训练营第23期day39 |62.不同路径、63. 不同路径 II

目录 一、&#xff08;leetcode 62&#xff09;不同路径 1.动态规划 1&#xff09;确定dp数组&#xff08;dp table&#xff09;以及下标的含义 2&#xff09;确定递推公式 3&#xff09;dp数组的初始化 4&#xff09;确定遍历顺序 5&#xff09;举例推导dp数组 2.数论方…...

白帽黑客入门,“每天一个黑客技巧”实现黑客的自我突破 !(附工具包!)

年底了&#xff0c;不少朋友都是在总结一年的学习成果。最后发现完成情况与自己最初定下的目标相去甚远。 同时也针对粉丝和网上大部分存在的问题进行了整理&#xff1a; “为什么我感觉学安全好难&#xff1f;” “渗透测试到底该怎么学&#xff1f;” “为什么总是挖不到漏…...

Jmeter参数化 —— 循环断言多方法

1、参数化接口测试数据 注意&#xff1a;csv文档参数化&#xff0c;里面有多少条数据&#xff0c;就要在线程组里循环多少次&#xff0c;不然就只执行一次 2、添加配置元件-计数器 关于计数器 ①Starting Value&#xff1a;给定计数器的初始值; ②递增&#xff1a;每次循环迭代…...

Autosar诊断实战系列26-Dem(DTCEvent)要点及配置开发详解

本文框架 前言1. Dem及其与其他模块交互介绍1.1 与DCM模块交互1.1.1 0x14服务调用时序1.1.2 0x85服务调用时序1.1.3 0x19服务调用时序1.2 与Fim模块交互1.3 与NvM模块交互1.4 与BswM模块交互1.5 与其他BSW及APP模块交互2. Dem配置开发介绍2.1 DemGeneral配置2.1.1 DemGeneral一…...

STL(第五课):queue

STL&#xff08;标准模板库&#xff09;是一种C标准库&#xff0c;在其中包含了许多常用的数据结构和算法。其中&#xff0c;queue就是STL库中的一个数据结构&#xff0c;用于实现队列&#xff08;先进先出FIFO&#xff09;。 使用STL queue&#xff0c;需要引入头文件<queu…...

点大商城V2版 2.5.2.1 全开源独立版 多小程序端+unipp安装教程

点大商城V2是一款采用全新界面设计支持多端覆盖的小程序应用&#xff0c;支持H5、微信公众号、微信小程序、头条小程序、支付宝小程序、百度小程序&#xff0c;本程序是点大商城V2独立版&#xff0c;包含全部插件&#xff0c;代码全开源&#xff0c;并且有VUE全端代码。分销&am…...

Redo Log(重做日志)的刷盘策略

1. 概述 Redo Log&#xff08;重做日志&#xff09;是 InnoDB 存储引擎中的一种关键组件&#xff0c;用于保障数据库事务的持久性和崩溃恢复。InnoDB 将事务所做的更改先记录到重做日志&#xff0c;之后再将其应用到磁盘上的数据页。 刷盘策略&#xff08;Flush Policy&#x…...

QT窗体之间值的传递,多种方法实现

目录 1. 信号和槽机制 2. 全局变量或单例模式 3. 事件过滤器 4. Qt属性系统 5. 使用QSettings类 在Qt中&#xff0c;有多种方法可以在窗体之间传递值。下面是一些常用的方法&#xff1a; 1. 信号和槽机制 使用Qt的信号和槽机制是一种常见的方式来在窗体之间传递值。您可以…...

政务服务技能竞赛中用到的软件和硬件

政务服务技能竞赛包括争上游、抢先机、秀风采、比擂台几个环节&#xff0c;用到选手端平板、评委端平板、主持人平板、抢答器等设备、抢答器等。分别计算团队分和个人分。答题规则和计分方案均较为复杂&#xff0c;一般竞赛软件无法实现&#xff0c;要用到高端竞赛软件&#xf…...

tcp/ip该来的还是得来

1. TCP/IP、Http、Socket的区别 \qquad 区别是&#xff1a;TCP/IP即传输控制/网络协议&#xff0c;也叫作网络通讯协议&#xff0c;它是在网络的使用中的最基本的通信协议。Http是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。Socket是对网络中不同主机上的应用进…...

OpenCV官方教程中文版 —— 图像修复

OpenCV官方教程中文版 —— 图像修复 前言一、基础二、代码三、更多资源 前言 本节我们将要学习&#xff1a; • 使用修补技术去除老照片中小的噪音和划痕 • 使用 OpenCV 中与修补技术相关的函数 一、基础 在我们每个人的家中可能都会几张退化的老照片&#xff0c;有时候…...

前端难学还是后端难学?系统安全,web安全,网络安全是什么区别?

系统安全&#xff0c;web安全&#xff0c;网络安全是什么区别&#xff1f;三无纬度安全问题 系统安全&#xff0c;可以说是电脑软件的安全问题&#xff0c;比如windows经常提示修复漏洞&#xff0c;是一个安全问题 网页安全&#xff0c;网站安全&#xff0c;比如&#xff0c;…...

diffusers-Load pipelines,models,and schedulers

https://huggingface.co/docs/diffusers/using-diffusers/loadinghttps://huggingface.co/docs/diffusers/using-diffusers/loading 有一种简便的方法用于推理是至关重要的。扩散系统通常由多个组件组成&#xff0c;如parameterized model、tokenizers和schedulers&#xff0c…...

私域营销必备:轻松掌握微信CRM管理方法

大家在微信私域营销中都遇到了什么问题&#xff1f; 比如管理时间不够&#xff0c;群发实效性低&#xff0c;自动回复无法适应变化等等。 我们可以利用微信CRM这个工具&#xff0c;轻松解决这些问题。 请问你们最想用这个工具解决什么问题呢&#xff1f; 使用微信CRM不仅可…...

最长回文子串-LeetCode5 动态规划

由于基础还不是很牢固 一时间只能想到暴力的解法: 取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3) class Solution { public:string longestPalindrome(string s) { int max0;string ret;for(int i0;i<s.size();i)for(int…...

mysql简单备份和恢复

版本&#xff1a;mysql8.0 官方文档 &#xff1a;MySQL :: MySQL 8.0 Reference Manual :: 7 Backup and Recovery 1.物理备份恢复 物理备份是以数据文件形式备份。这种方式效率高点&#xff0c;适合大型数据库备份。物理备份可冷备可热备。 使用mysqlbackup 命令进行物理备…...

JMeter介绍

1. JMeter是什么&#xff1f; 是Apache组织开发基于Java的接口测试工具&#xff0c;性能测试工具 2.JMeter的优缺点 优点&#xff1a; 开源&#xff0c;免费 跨平台 支持多协议 轻量级别 缺点&#xff1a; 不支持IP欺骗 不可验证页面UI 3.JMeter可以用来做什么&#xff1f; …...

flink job同时使用BroadcastProcessFunction和KeyedBroadcastProcessFunction例子

背景&#xff1a; 广播状态可以用于规则表或者配置表的实时更新&#xff0c;本文就是用一个欺诈检测的flink作业作为例子看一下BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 1.首先看主流…...

数据中心系统解决方案

设计思路 系统设计过程中充分考虑各个子系统的信息共享要求&#xff0c;对各子系统进行结构化和标准化设计&#xff0c;通过系统间的各种联动方式将其整合成一个有机的整体&#xff0c;使之成为一套整体的、全方位的数据中心大楼综合管理系统&#xff0c;达到人防、物防和技防…...

服务器开设新账户,创建账号并设置密码

实验室又进新同学了&#xff0c;服务器开设新账号搞起来 1、创建用户&#xff1a; 在root权限下&#xff0c;输入命令useradd -m 用户名&#xff0c;如下 sudo useradd -m yonghuming 2、设置密码&#xff1a; 输入命令passwd 用户名 回车&#xff0c;接着输入密码操作&…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...