代码随想录训练营第三十九天|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 是一个动漫模型,画风色彩鲜明,擅长绘制漂亮的小姐姐。 条目内容类型大模型…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...