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

代码随想录训练营第三十九天|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数组&#xff08;dp table&#xff09;以及下标的含义 从&#xff08;0&#xff0c;0&#xff09;出发到&#xff08;i&#xff0c;j&#xff09;有 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 光速入门课程

首先说一下&#xff0c;为啥小编在即PHP和Golang之后&#xff0c;为啥又要整Python&#xff0c;那是因为小编最近又拿起了 " 阿里天池 " 的东西&#xff0c;所以小编又不得不捡起来大概五年前学习的Python&#xff0c;本篇文章主要讲的是最基础版本&#xff0c;所以比…...

解决vite打包出现 “default“ is not exported by “node_modules/...问题

项目场景&#xff1a; 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函数的作用为以指定字符分割字符串&#xff0c;含有两个参数&#xff0c;第一个函数为待分割的字符串或者空指针NULL&#xff0c;第二个参数为分割字符集。 对一个字符串首次使用strtok时第一个参数应该是待分割字符串&#xff0c;strtok以指定字符完成第一次分割后&…...

hash,以及数据结构——map容器

1.hash是什么&#xff1f; 定义&#xff1a;hash,一般翻译做散列、杂凑&#xff0c;或音译为哈希&#xff0c;是把任意长度的输入&#xff08;又叫做预映射pre-image&#xff09;通过散列算法变换成固定长度的输出&#xff0c; 该输出就是散列值。这种转换是一种压缩映射&…...

AIoT网关 人工智能物联网网关

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

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的鸟类识别系统(Python+PySide6界面+训练代码)

摘要&#xff1a;本文详细阐述了一个利用深度学习进行鸟类识别的系统&#xff0c;该系统集成了最新的YOLOv8算法&#xff0c;并与YOLOv7、YOLOv6、YOLOv5等先前版本进行了性能比较。该系统能够在图像、视频、实时视频流和批量文件中精确地识别和分类鸟类。文中不仅深入讲解了YO…...

核密度分析

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

先进语言模型带来的变革与潜力

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

重铸安卓荣光——上传图片组件

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

Bert基础(四)--解码器(上)

1 理解解码器 假设我们想把英语句子I am good&#xff08;原句&#xff09;翻译成法语句子Je vais bien&#xff08;目标句&#xff09;。首先&#xff0c;将原句I am good送入编码器&#xff0c;使编码器学习原句&#xff0c;并计算特征值。在前文中&#xff0c;我们学习了编…...

Visual Studio快捷键记录

日常使用Visual Studio进行开发&#xff0c;记录一下常用的快捷键&#xff1a; 复制&#xff1a;CtrlC剪切&#xff1a;CtrlX粘贴&#xff1a;CtrlV删除&#xff1a;CtrlL撤销&#xff1a;CtrlZ反撤销&#xff1a;CtrlY查找&#xff1a;CtrlF/CtrlI替换&#xff1a;CtrlH框式选…...

分享84个Html个人模板,总有一款适合您

分享84个Html个人模板&#xff0c;总有一款适合您 84个Html个人模板下载链接&#xff1a;https://pan.baidu.com/s/1GXUZlKPzmHvxtO0sm3gHLg?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集…...

vue使用.sync和update实现父组件与子组件数据绑定的案例

在 Vue 中&#xff0c;.sync 是一个用于实现双向数据绑定的特殊修饰符。它允许父组件通过一种简洁的方式向子组件传递一个 prop&#xff0c;并在子组件中修改这个 prop 的值&#xff0c;然后将修改后的值反馈回父组件&#xff0c;实现双向数据绑定。 使用 .sync 修饰符的基本语…...

C语言系列15——C语言的安全性与防御性编程

目录 写在开头1 缓冲区溢出&#xff1a;如何防范与处理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为空&#xff01;";}if ( content.lengt…...

2024开年,手机厂商革了自己的命

文&#xff5c;刘俊宏 编&#xff5c;王一粟 2024开年&#xff0c;AI终端的号角已经由手机行业吹响。 OPPO春节期间就没闲着&#xff0c;首席产品官刘作虎在大年三十就迫不及待地宣布&#xff0c;OPPO正式进入AI手机时代。随后在开年后就紧急召开了AI战略发布会&#xff0c;…...

【安全】大模型安全综述

大模型相关非安全综述 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绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五 下载地址 模型介绍 AstrAnime 是一个动漫模型&#xff0c;画风色彩鲜明&#xff0c;擅长绘制漂亮的小姐姐。 条目内容类型大模型…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式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、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 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…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...