【代码随想录算法训练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值&#…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
Python常用模块:time、os、shutil与flask初探
一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...

【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...

VSCode 使用CMake 构建 Qt 5 窗口程序
首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...
当下AI智能硬件方案浅谈
背景: 现在大模型出来以后,打破了常规的机械式的对话,人机对话变得更聪明一点。 对话用到的技术主要是实时音视频,简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术,开发自己的大模型。商用方案多见为字节、百…...

spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...