【代码随想录算法训练Day39】LeetCode 62.不同路径、LeetCode 63.不同路径II
Day39 动态规划第二天
LeetCode 62.不同路径
二维dp数组的含义:走到位置为(i,j)的格子的走法为dp[i][j]种。
递推公式:dp[i][j]=dp[i-1][j]+dp[i][j-1]。
初始化:dp[i][0]和dp[0][j]都赋值为1.
递归顺序:从左往右,从上到下。
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];}
};
LeetCode 63.不同路径II
二维dp数组的含义:走到位置为(i,j)的格子的走法为dp[i][j]种.
递推公式:没有障碍,即obs[i][j]==0时,dp[i][j]=dp[i-1][j]+dp[i][j-1]。
※初始化:没遇到障碍时,dp[i][0]和dp[0][j]都赋值为1,遇到障碍后,后面全是0.
遍历顺序:从左往右,从上到下。
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size(),n=obstacleGrid[0].size();vector<vector<int>> dp(m,vector<int>(n,0));if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) return 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];}
};
动态规划有点感觉了。
相关文章:
【代码随想录算法训练Day39】LeetCode 62.不同路径、LeetCode 63.不同路径II
Day39 动态规划第二天 LeetCode 62.不同路径 二维dp数组的含义:走到位置为(i,j)的格子的走法为dp[i][j]种。 递推公式:dp[i][j]dp[i-1][j]dp[i][j-1]。 初始化:dp[i][0]和dp[0][j]都赋值为1. 递归顺序:从左往右,从上…...

浙大版PTA Python程序设计 题目与知识点整理(综合版)
目录 第一章 一、高级语言程序的执行方式 二、变量赋值与内存地址 三、字符编码 3.1 Unicode 3.2 ASCII(American Standard Code for Information Interchange) 四、编程语言分类按照编程范式分类 4.1 面向过程语言 4.2 面向对象语言 五、原码…...

HTML表单深度解析:构建互动的网页界面
表单是HTML中用于收集用户输入信息的重要元素,是网页与用户交互的关键组件。以下是一个典型的HTML表单示例,我们将会详细解析其中的各个元素及属性含义。 <form action"https://xx.xxx.xx/search" target"_self" method"ge…...
git 分支管理规范
分支命名 master 分支 master 为主分支,也是用于部署生产环境的分支,需要确保master分支稳定性。master 分支一般由 release 以及 hotfix 分支合并,任何时间都不能直接修改代码。 develop 分支 develop 为开发环境分支,始终保持…...

Spring Cloud Gateway 详解:构建高效的API网关解决方案
Spring Cloud Gateway 详解:构建高效的API网关解决方案 Spring Cloud Gateway 是 Spring Cloud 生态系统中用于构建 API 网关的核心组件。它基于 Spring WebFlux 构建,旨在提供简单且有效的方式来路由和增强 API 请求。以下是 Spring Cloud Gateway 的详…...

基于Quartus Prime18.1的安装与FPGA的基础仿真教程
Quartus是一种美国科技公司Intel(英特尔)公司开发的FPGA(现场可编辑门阵列)设计编译软件,用作设计、仿真、综合和布局、支持多种编程语言,包括VHDL、Verilog等,并具有丰富的功能和工具库&#x…...
AJAX 和 XML:现代 Web 开发的关键技术
AJAX 和 XML:现代 Web 开发的关键技术 引言 在当今的 Web 开发领域,AJAX 和 XML 是两项至关重要的技术。AJAX(Asynchronous JavaScript and XML)允许网页在不重新加载整个页面的情况下,与服务器交换数据和更新部分网页内容。而 XML(eXtensible Markup Language)则是一…...
vue实现图片预览
在 Vue 中实现图片预览功能,通常涉及监听文件输入的变化,并在用户选择文件后,使用 FileReader API 来读取文件内容,然后显示这个内容作为图片的预览。以下是一个简单的 Vue 组件示例,它实现了图片预览功能:…...

C语言入门系列:流程控制
一,C代码执行顺序 默认情况下,C语言程序从main()函数开始执行,随后按源代码中语句出现的顺序逐一执行。 这意味着,如果不考虑任何控制结构,程序会自上而下,逐行执行每条语句,直到遇到函数调用…...

【深度学习】NLP,Transformer讲解,代码实战
文章目录 1. 前言2. Transformer结构训练过程1. 输入嵌入和位置编码2. 编码器层2.1 单头的注意力机制(便于理解)2.2 多头的注意力机制(Transformer真实使用的)2.3 残差连接和层归一化2.4 前馈神经网络(FFN)2.5 残差连接和层归一化2.6 总结 3. 解码器层 推…...
ES6 .entries用法
.entries() 返回数组的可迭代对象itarator,可以通过for of 来遍历数组或对象的值。但是它们的写法不一样。 数组用法 obj [apple,bananer,orange] for(let [i,v] of obj.entries()){console.log(i)console.log(v) } //输出 // 0 // apple // 1 // bananer // 2 //orange对象…...

【LeetCode 动态规划】买卖股票的最佳时机问题合集
文章目录 1. 买卖股票的最佳时机含冷冻期 1. 买卖股票的最佳时机含冷冻期 题目链接🔗 🍎题目思路: 🍎题目代码: class Solution { public:int maxProfit(vector<int>& prices) {int n prices.size();ve…...
python学习:语法(2)
目录 对象的布尔值 分支结构 双分支结构 多分支结构 嵌套if的使用 条件表达式 Pass语句 range()函数的使用 流程控制语句 对象的布尔值 Python一切皆对象,所有对象都有一个布尔值,通过内置函数bool()获取对象的布尔值 这些…...

经典电源电路基础(变压-整流-滤波-稳压)
1.电源电路的功能和组成 电子电路中的电源一般是低压直流电,先把220v交流电变换成低压直流电,再用整流电路变成脉动的直流电,最后用滤波电路滤除掉脉动直流中的交流成分后才能得到直流电。有的电子设备对电源的质量要求很高,所以…...

生成式人工智能备案办理指南,深度解析大模型备案全流程
早在2023年年初,国家互联网信息办公室、工业和信息化部、公安部针对深度合成服务制定的《互联网信息服务深度合成管理规定》(“《深度合成管理规定》”)顺利施行,其明确了深度合成服务相关方的义务与主体责任,强化了对…...
1527. 患某种疾病的患者
1527. 患某种疾病的患者 题目链接:1527. 患某种疾病的患者 代码如下: # Write your MySQL query statement below select patient_id,patient_name,conditions from Patients where conditions like "DIAB1%" or conditions like "% DI…...

【C/C++】【学生成绩管理系统】深度剖析
可接各类C/C管理系统课设 目录 实现功能 部分1:系统设置和主菜单 1. 引入头文件 2. 定义结构体 3. 函数声明 4. 主函数 部分2:添加学生信息 部分3:删除学生信息 部分4:修改学生信息 部分5:查询学生信息 部分…...
C++作业第四天
#include <iostream> using namespace std; class Per { private: string name; int age; int *high; double *weight; public: //构造函数 Per() { cout << "Per的无参构造" << endl; } Per(str…...

设计模式之工厂方法模式(Factory Method Pattern)
目录 1.1、前言1.2、工厂方法模式简介1.2.1、工厂方法模式的主要特点1.2.2、工厂方法模式的主要结构1.2.3、使用工厂方法模式的好处 1.3、SpringBoot中那些场景使用了工厂方法模式1.4、日常工作中那些业务场景可以使用工厂方法模式1.5、工厂方法模式实战(以某商场一…...
API接口设计的18条规范
API接口设计的18条规范 签名 目的:防止数据被篡改 实现方法: 接口请求方将请求参数、时间戳和密钥拼接成一个字符串使用MD5等hash算法生成签名sign在请求参数或请求头中增加sign参数,传递给API接口API接口网关服务验证传递的sign值&#…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

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

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
StarRocks 全面向量化执行引擎深度解析
StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计,相比传统行式处理引擎(如MySQL),性能可提升 5-10倍。以下是分层拆解: 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...