代码随想录训练营第三十九天|62.不同路径63. 不同路径 II
62.不同路径
1确定dp数组(dp table)以及下标的含义
从(0,0)出发到(i,j)有 dp[i][j]种路径
2确定递推公式
dp[i][j]=dp[i-1][j]+dp[i][j-1]
3dp数组如何初始化
for(int i=0;i<m;i++)
dp[i][0] = 1;
for(int j=0;j<n;j++)
dp[0][j] = 1;
4确定遍历顺序
从左上到右下
5举例推导dp数组、
m=2,n=2时dp[1][1]=2
class Solution {
public:int uniquePaths(int m, int n) {if(m<=0&&n<=0)return 0;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];}
};
63. 不同路径 II
1确定dp数组(dp table)以及下标的含义
从(0,0)出发到(i,j)有 dp[i][j]种路径
2确定递推公式
if(obstacleGrid[i][j]==0){dp[i][j]=dp[i-1][j]+dp[i][j-1]}
3dp数组如何初始化
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[j][0]=1;
4确定遍历顺序
从左上到右下
5举例推导dp数组
obstacleGrid=[[0,0,0][0,1,0][0,0,0]]
dp[2][2]=2
class Solution
{
public:int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid){int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1){return 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] == 0){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
};
相关文章:
代码随想录训练营第三十九天|62.不同路径63. 不同路径 II
62.不同路径 1确定dp数组(dp table)以及下标的含义 从(0,0)出发到(i,j)有 dp[i][j]种路径 2确定递推公式 dp[i][j]dp[i-1][j]dp[i][j-1] 3dp数组如何初始化 for(int i0;i<m…...

学习大数据所需的java基础(5)
文章目录 集合框架Collection接口迭代器迭代器基本使用迭代器底层原理并发修改异常 数据结构栈队列数组链表 List接口底层源码分析 LinkList集合LinkedList底层成员解释说明LinkedList中get方法的源码分析LinkedList中add方法的源码分析 增强for增强for的介绍以及基本使用发2.使…...

Python 光速入门课程
首先说一下,为啥小编在即PHP和Golang之后,为啥又要整Python,那是因为小编最近又拿起了 " 阿里天池 " 的东西,所以小编又不得不捡起来大概五年前学习的Python,本篇文章主要讲的是最基础版本,所以比…...
解决vite打包出现 “default“ is not exported by “node_modules/...问题
项目场景: vue3tsvite项目打包 问题描述 // codemirror 编辑器的相关资源 import Codemirror from codemirror;error during build: RollupError: "default" is not exported by "node_modules/vue/dist/vue.runtime.esm-bundler.js", impor…...
c语言strtok的使用
strtok函数的作用为以指定字符分割字符串,含有两个参数,第一个函数为待分割的字符串或者空指针NULL,第二个参数为分割字符集。 对一个字符串首次使用strtok时第一个参数应该是待分割字符串,strtok以指定字符完成第一次分割后&…...

hash,以及数据结构——map容器
1.hash是什么? 定义:hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出, 该输出就是散列值。这种转换是一种压缩映射&…...

AIoT网关 人工智能物联网网关
AIoT(人工智能物联网)作为新一代技术的代表,正以前所未有的速度改变着我们的生活方式。在这个智能时代,AIoT网关的重要性日益凸显。它不仅是连接智能设备和应用的关键,同时也是实现智能化家居、智慧城市和工业自动化的必备技术。 一…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的鸟类识别系统(Python+PySide6界面+训练代码)
摘要:本文详细阐述了一个利用深度学习进行鸟类识别的系统,该系统集成了最新的YOLOv8算法,并与YOLOv7、YOLOv6、YOLOv5等先前版本进行了性能比较。该系统能够在图像、视频、实时视频流和批量文件中精确地识别和分类鸟类。文中不仅深入讲解了YO…...

核密度分析
一.算法介绍 核密度估计(Kernel Density Estimation)是一种用于估计数据分布的非参数统计方法。它可以用于多种目的和应用,包括: 数据可视化:核密度估计可以用来绘制平滑的密度曲线或热力图,从而直观地表…...

先进语言模型带来的变革与潜力
用户可以通过询问或交互方式与GPT-4这样的先进语言模型互动,开启通往知识宝库的大门,即时访问人类历史积累的知识、经验与智慧。像GPT-4这样的先进语言模型,能够将人类历史上积累的海量知识和经验整合并加以利用。通过深度学习和大规模数据训…...

重铸安卓荣光——上传图片组件
痛点: 公司打算做安卓软件,最近在研究安卓,打算先绘制样式 研究发现安卓并不像前端有那么多组件库,甚至有些基础的组件都需要自己实现,记录一下自己实现的组件 成品展示 一个上传图片的组件 可以选择拍照或者从相册中…...

Bert基础(四)--解码器(上)
1 理解解码器 假设我们想把英语句子I am good(原句)翻译成法语句子Je vais bien(目标句)。首先,将原句I am good送入编码器,使编码器学习原句,并计算特征值。在前文中,我们学习了编…...
Visual Studio快捷键记录
日常使用Visual Studio进行开发,记录一下常用的快捷键: 复制:CtrlC剪切:CtrlX粘贴:CtrlV删除:CtrlL撤销:CtrlZ反撤销:CtrlY查找:CtrlF/CtrlI替换:CtrlH框式选…...

分享84个Html个人模板,总有一款适合您
分享84个Html个人模板,总有一款适合您 84个Html个人模板下载链接:https://pan.baidu.com/s/1GXUZlKPzmHvxtO0sm3gHLg?pwd8888 提取码:8888 Python采集代码下载链接:采集代码.zip - 蓝奏云 学习知识费力气,收集…...
vue使用.sync和update实现父组件与子组件数据绑定的案例
在 Vue 中,.sync 是一个用于实现双向数据绑定的特殊修饰符。它允许父组件通过一种简洁的方式向子组件传递一个 prop,并在子组件中修改这个 prop 的值,然后将修改后的值反馈回父组件,实现双向数据绑定。 使用 .sync 修饰符的基本语…...
C语言系列15——C语言的安全性与防御性编程
目录 写在开头1 缓冲区溢出:如何防范与处理1.1 缓冲区溢出的原因1.2 预防与处理策略 2. 安全的字符串处理函数与使用技巧2.1 strncpy函数2.2 snprintf函数2.3 strlcpy函数2.4 使用技巧 3 防御性编程的基本原则与实际方法3.1 基本原则3.2 实际方法 写在最后 写在开头…...
objectMapper、ObjectNode、JsonNode调用接口时进行参数组装
objectMapper、ObjectNode、JsonNode用于调用接口时进行参数组装 public String sendText( List< String > listUser, String content ) throws JsonProcessingException{if ( listUser.size() < 0 ){return "用户ID为空!";}if ( content.lengt…...

2024开年,手机厂商革了自己的命
文|刘俊宏 编|王一粟 2024开年,AI终端的号角已经由手机行业吹响。 OPPO春节期间就没闲着,首席产品官刘作虎在大年三十就迫不及待地宣布,OPPO正式进入AI手机时代。随后在开年后就紧急召开了AI战略发布会,…...
【安全】大模型安全综述
大模型相关非安全综述 LLM演化和分类法 A survey on evaluation of large language models,” arXiv preprint arXiv:2307.03109, 2023.“A survey of large language models,” arXiv preprint arXiv:2303.18223, 2023.“A survey on llm-gernerated text detection: Necess…...

Stable Diffusion 模型分享:AstrAnime(Astr动画)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五 下载地址 模型介绍 AstrAnime 是一个动漫模型,画风色彩鲜明,擅长绘制漂亮的小姐姐。 条目内容类型大模型…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...