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

动态规划5:62. 不同路径

动态规划解题步骤:

1.确定状态表示:dp[i]是什么

2.确定状态转移方程:dp[i]等于什么

3.初始化:确保状态转移方程不越界

4.确定填表顺序:根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接:62. 不同路径 - 力扣(LeetCode)

题解:

1. 状态表示:dp[i]表示到达[i,j]位置有几种方法

2.状态转移方程:dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.初始化:初始化第一行和第一列,值为1

4.填表顺序:遍历二维数组依次填写

5.返回值:dp[m-1][n-1]

class Solution {
public:int uniquePaths(int m, int n) {//创建dp表vector<vector<int>> dp(m);for(int i=0;i<m;++i) dp[i].resize(n);//初始化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];}
};//dp[i][j]=dp[i-1][j]+dp[i][j-1]

优化题解:

将初始化与填表合并,但是为了防止填表越界,需要多开一行一列空间,并且多开的空间需要填入合适的值以保证填表正确。本题需要使dp[0][1]=1,其余位置为0。注意返回值改变!

class Solution {
public:int uniquePaths(int m, int n) {//创建dp表(多开一行一列)vector<vector<int>> dp(m+1,vector<int>(n+1));//多开位置填值dp[0][1]=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][n];}
};

相关文章:

动态规划5:62. 不同路径

动态规划解题步骤&#xff1a; 1.确定状态表示&#xff1a;dp[i]是什么 2.确定状态转移方程&#xff1a;dp[i]等于什么 3.初始化&#xff1a;确保状态转移方程不越界 4.确定填表顺序&#xff1a;根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接&#xff1a;62. …...

Python编程学习第一篇——Python零基础快速入门(五)-列表(List)

今天我们来一起学习Python的列表&#xff08;list&#xff09;&#xff0c;Python中的列表&#xff08;List&#xff09;是一种有序、可变的数据结构&#xff0c;可以用来存储多个值。列表可以包含不同类型的数据&#xff0c;例如整数、浮点数、字符串等。以下是关于Python列表…...

c# - 运算符 << 不能应用于 long 和 long 类型的操作数

Compiler Error CS0019 c# - 运算符 << 不能应用于 long 和 long 类型的操作数 处理方法 特此记录 anlog 2024年5月30日...

问题排查|记录一次基于mymuduo库开发的服务器错误排查(回响服务器无法正常工作)

问题背景&#xff1a; 服务器程序如下&#xff1a; #include <mymuduo/TcpServer.h> #include <mymuduo/Logger.h>#include <string> #include <functional>class EchoServer { public:EchoServer(EventLoop *loop,const InetAddress &addr, con…...

中介模式实现聊天室

中介者模式的核心逻辑就是解耦对象‘多对多’的相互依赖关系。当遇到一大堆混乱的对象呈现“网状结构”&#xff0c;利用通过中介者模式解耦对象之间的通讯。 代码案例 抽象中介类 public abstract class AbstractChatRoom {public abstract void notice(String message , Us…...

游戏开发与游戏设计区别

游戏设计与游戏开发是两个紧密相关但有着不同重点的领域&#xff0c;通常需要不同的技能和流程。以下是对游戏设计与游戏开发的详细解释&#xff0c;以及两者的区别&#xff1a; 游戏设计是关于构思和规划游戏的内容、机制和体验的过程。 主要内容: 故事和情节&#xff1a;构…...

卡尔曼滤波算法的matlab实现

卡尔曼滤波算法的matlab实现 figure; hold on;Z(1:1:100); %观测值&#xff1a;第一秒观测1m 第二秒观测两米 匀速运动, 每秒1m, 最后拟合的也是速度 1m/splot(Z); plot([0,100], [1,1]);noiserandn(1,100)*0.5; %生成方差为1的高斯噪声 ZZnoise; % 加入噪声plot(Z);X[0;…...

Unity Obi Rope失效

文章目录 前言一、WebGL端Obi Rope失效二、Obi Rope 固定不牢三、使用Obi后卡顿总结 前言 Obi 是一款基于粒子的高级物理引擎&#xff0c;可模拟各种可变形材料的行为。 使用 Obi Rope&#xff0c;你可以在几秒内创建绳索和杆子&#xff0c;同时完全控制它们的形状和行为&…...

基于Nginx和Consul构建自动发现的Docker服务架构——非常之详细

基于Nginx和Consul构建自动发现的Docker服务架构 文章目录 基于Nginx和Consul构建自动发现的Docker服务架构资源列表基础环境一、安装Docker1.1、Consul节点安装1.2、registrator节点安装 二、案例前知识点2.1、什么是Consul 三、基于Nginx和Consul构建自动发现的Docker服务架构…...

Gnu/Linux 系统编程 - 如何获取帮助及一个演示

Gnu/Linux 系统编程 - 如何获取帮助及一个演示 今天开始写 Gnu/Linux 环境下的系统编程&#xff0c;主要的用的语言是 C&#xff0c;主要是为了学习 C 语言&#xff0c;边学边写&#xff0c;这样的学习速度是比较快的。 今天就先介绍下如何在手头上没有任何资料的情况下&…...

ffmpeg 的sws_scale接口函数解析

ffmpeg 的 sws_scale 函数是 libswscale 库中的一个重要函数&#xff0c;用于进行图像的缩放和颜色空间转换。它的主要作用是将输入图像帧转换为另一种尺寸或颜色格式的输出图像帧。下面详细解析一下 sws_scale 函数的作用、参数等。 sws_scale 函数的作用 ffmpeg 的 sws_sca…...

MoonBit 本周新增类型标注语法、继续进行核心库 API 整理工作

MoonBit更新 类型标注增加了新的语法T? 来表示Option[T] struct Cell[T] {val: Tnext: Cell[T]? }fn f(x : Cell[T]?) -> Unit { ... }相当于 struct Cell[T] {val: Tnext: Option[Cell[T]] }fn f(x : Option[Cell[T]]) -> Unit { ... }旧的Option[T]仍然兼容&…...

YOLOv10训练自己的数据集

目录 0、引言 1、环境配置 2、数据集准备 3、创建配置文件 3.1、设置官方配置文件&#xff1a;default.yaml&#xff0c;可自行修改。 3.2、设置data.yaml 4、进行训练 4.1、方法一 4.2、方法二 5、验证模型 5.1、命令行输入 5.2、脚本运行 6、总结 0、引言 本文…...

探索Web前端三大主流框架:Angular、React和Vue.js

探索Web前端三大主流框架&#xff1a;Angular、React和Vue.js 在现代Web开发中&#xff0c;前端框架已经成为开发者构建复杂应用的重要工具。Angular、React和Vue.js是目前最受欢迎的三大前端框架&#xff0c;它们各具特色&#xff0c;适用于不同的开发需求。本文将详细介绍这…...

《HelloGitHub》第 98 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 Python、…...

Xtransfer面试内容

一、Xtransfer一轮面试内容 1.进程间的通信方式 2.redis的故障转移是如何选举主节点的 3.redis快的原因 4.redis、ES、mysql选型的场景 5.redis项目的挑战和难点 6.redis和ZK各自的应用场景 7.ZK选举的算法 8.socket建立连接的过程&#xff0c;与TCP是一回事吗&#xff1f; So…...

论文笔记:Image Anaimation经典论文-运动关键点模型(Monkey-Net)

Monkey-Net&#xff08;MOviNg KEYpoints&#xff09; paper: https://arxiv.org/pdf/1812.08861, CVPR 2019 code: https://github.com/AliaksandrSiarohin/monkey-net/tree/master 相关工作 视频生成演变过程&#xff1a; spatio-temporal network: 如基于GAN网络的生成模…...

Kibana创建ElasticSearch 用户角色

文章目录 1, ES 权限参考2, 某应用的管理员权限&#xff1a;可以open/close/delete/cat/read/write 索引3, 某应用的读写权限&#xff1a;可以cat/read/write 索引 &#xff08;不能删除索引或数据&#xff09;4, 某应用的只读权限 1, ES 权限参考 https://www.elastic.co/gui…...

Vue基础(2)响应式基础

一. reactive() 在 Vue3 中&#xff0c;可以使用 reactive() 创建一个响应式对象或数组&#xff1a; <script setup> import { reactive } from vueconst state reactive({ count: 0 }) </script><template><button click"state.count">{…...

Mysql基础教程(15):别名

MySQL 别名 在本文中&#xff0c;我们讨论了 MySQL 中的列别名&#xff0c;表别名和派生表别名&#xff0c;以及使用别名来简化 SQL 和提高 SQL 的可读性。 如果在一个 SQL 中涉及到多个表&#xff0c;我们需要使用 table_name.column_name 这样的方式来引用每个表的字段&…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...