Leetcode 64. 最小路径和 动态规划+空间优化

原题链接:Leetcode 64. 最小路径和
在这里插入图片描述
二维数据

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int dp[m][n];dp[0][0] = grid[0][0];for (int j = 1; j < n; j++)dp[0][j] = dp[0][j - 1] + grid[0][j];for (int i = 1; i < m; i++)dp[i][0] = dp[i - 1][0] + grid[i][0];for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[m - 1][n - 1];}
};

一维数组,空间优化:

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int dp[n];dp[0] = grid[0][0];for (int j = 1; j < n; j++)dp[j] = dp[j - 1] + grid[0][j];for (int i = 1; i < m; i++) {for (int j = 0; j < n; j++) {if (j == 0) {dp[j] += grid[i][j];} else {dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];}}}return dp[n - 1];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/2168.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

qt QMenu详解

1、概述 QMenu是Qt框架中的一个类&#xff0c;用于创建和管理菜单。它提供了丰富的接口来添加菜单项&#xff08;通常是QAction对象&#xff09;、子菜单以及分隔符。QMenu可以嵌入到菜单栏&#xff08;QMenuBar&#xff09;中&#xff0c;也可以作为弹出菜单&#xff08;通过…

Android——Activity生命周期

Activity生命周期 onCreate&#xff1a;创建活动。把页面布局加载进内存&#xff0c;君如了初始状态。onStart&#xff1a;开始活动。把活动页面显示在屏幕上&#xff0c;进入了就绪状态。onResume&#xff1a;恢复活动。活动页面进入活跃状态&#xff0c;能够与用户正常交互&…

02- 模块化编程-004 DB18B20温度数码显示

1、DB18B20采样与显示电路 2、DB18B20简介 DS18B20是一款高精度的单总线数字温度传感器&#xff0c;适用于多种温度测量场合。 温度范围&#xff1a;-55℃至125℃精度&#xff1a;可编程设定9至12位分辨率&#xff0c;对应温度分辨率0.5℃、0.25℃、0.125℃、0.0625℃通信&am…

[241102] Fedora Linux 41 正式发布 | Wasmer 5.0 发布

目录 Fedora Linux 41 正式发布Wasmer 5.0 发布 Fedora Linux 41 正式发布 主要更新&#xff1a; DNF 5: 更快、更小、依赖更少&#xff0c;统一了容器、服务器、桌面和设备的包管理体验。桌面更新&#xff1a; Fedora Workstation 41 基于 GNOME 47&#xff0c;默认终端改为…

C++继承

文章目录 一、继承的概念和定义1、继承的概念2、继承的定义3、继承基类成员访问方式的变化 二、基类和派生类之间的转换三、继承中的作用域1、隐藏规则 四、派生类的默认成员函数1、常见默认成员函数2、实现一个不能被继承的类 五、继承与友元六、继承与静态成员变量七、多继承…

嵌入式linux系统中串口驱动框架分析

大家好,今天主要给大家分享一下,如何使用linux系统中的串口实现。 第一:串口基本简介 串口是很常见的一个外设,在Linux下通常通过串口和其他设备或传感器进行通信。根据电平的不同,串口可以分为TTL和RS232。不管是什么样的电平接口,驱动程序是一样的。 第二:Linux下UAR…

秋日盛景,北京马拉松万人齐跑,秀域人工智能理疗获好评无数

在金秋送爽的北京&#xff0c;一场全民瞩目的体育盛事——北京马拉松顺利开跑&#xff0c;再次点燃了这座城市的运动激情。各地跑者齐聚双奥之城&#xff0c;共同奔赴在秋日美景之中。      回首往昔&#xff0c;1981年9月27日&#xff0c;首届北京马拉松赛的举办&#xff…

Java-I/O框架09:InputStreamReader、OutputStreamWriter使用

视频链接&#xff1a;16.24 转换流的使用_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Tz4y1X7H7?spm_id_from333.788.videopod.episodes&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5&p24 1.InputStreamReader使用 package com.yundait.Demo05;import java…

JavaScript语法基础(JS使用方式, 输出方式, 变量,数据类型,运算符,程序控制语句)

目录 JS概念 一.JS使用方式 &#xff08;1&#xff09;行内式 &#xff08;2&#xff09;内嵌式 &#xff08;3&#xff09;外链式 二.JS输出方式 三.基本语法 1.变量 &#xff08;1&#xff09;变量的命名 &#xff08;2&#xff09;变量的声明 &#xff08;3&#xf…

NPOI 操作详解(操作Excel)

目录 1. 安装 NPOI 2. 使用 NPOI 创建新 Excel 文件 3. 设置列宽和行高 1. 设置列宽 2. 设置行高 3. 同时设置列宽和行高 4. 设置统一的行高 5. 设置统一的列宽 6. 应用统一的行高和列宽 4. 合并单元格 5. 设置单元格样式&#xff08;字体、边框、背景色等&#xf…

codigger体验过程记录

一、codigger的介绍 codigger是一款分布式操作系统&#xff0c;主要是便于进行个人移动化办公、在线协同办公、开发和娱乐的私人应用。 收到codigger开发者朋友的邀请&#xff0c;于是进行了这款产品的升级体验&#xff0c;接下来就简单介绍一下自己的体验过程吧。 二、登录系…

使用labelme中的AI模型提升数据标注速度

1、打开labelme 2、选择AI模型 选择之后&#xff0c;会自动进行模型下载&#xff0c;推荐开梯子&#xff0c;否则可能下载失败&#xff0c;最小的EfficientSam 在30M左右 3、右键选择AI多边形&#xff08;分割&#xff09;或AI蒙版&#xff08;目标检测&#xff09;&#xf…

全双工通信协议WebSocket——使用WebSocket实现智能学习助手/聊天室功能

一.什么是WebSocket&#xff1f; WebSocket是基于TCP的一种新的网络协议。它实现了浏览器与服务器的全双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c;并进行双向数据传输 HTTP 协议是一种无状态的、无连接的、单向的应用…

音乐网站新篇章:SpringBoot Web实现

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

【初阶数据结构篇】链式结构二叉树(二叉链)的实现(感受递归暴力美学)

文章目录 须知 &#x1f4ac; 欢迎讨论&#xff1a;如果你在学习过程中有任何问题或想法&#xff0c;欢迎在评论区留言&#xff0c;我们一起交流学习。你的支持是我继续创作的动力&#xff01; &#x1f44d; 点赞、收藏与分享&#xff1a;觉得这篇文章对你有帮助吗&#xff1…

el-talble selection行 初始默认勾选

导言 el-talble selection 行&#xff08;选择列&#xff09;用于显示复选框&#xff0c;让用户可以选择或取消选择某些表格行&#xff0c;常用于批量操作场景。 刚刚试了下&#xff0c;想加深印象记录一下当学习碎片。参考的是表格多选并根据每行值初始化选中状态&#xff08;…

RabbitMQ交换机类型

RabbitMQ交换机类型 1、RabbitMQ工作模型2、RabbitMQ交换机类型2.1、Fanout Exchange&#xff08;扇形&#xff09;2.1.1、介绍2.1.2、示例2.1.2.1、生产者2.1.2.2、消费者2.1.2.3、测试 2.2、Direct Exchange&#xff08;直连&#xff09;2.2.1、介绍2.2.2、示例2.2.2.1、生产…

数据结构---排序(上)

一.直接插入排序 思想&#xff1a;将一个个未排序的数字插入到已经排好顺序的数组中。 例如&#xff1a; 思路&#xff1a;先将前两个数字排序&#xff0c;然后将后面数字与前面数字比较排序。 操作&#xff1a; 1.引入变量 i 遍历数组[1&#xff0c;array.lenth] 2.用临时…

ai翻唱部分步骤

模型部署 我是用的RVC进行的训练&#xff0c;也可以使用so-vits-svc。 通过百度网盘分享的文件&#xff1a;RVC-beta 链接&#xff1a;https://pan.baidu.com/s/1c99jR2fLChoqUFqf9gLUzg 提取码&#xff1a;4090 以Nvida显卡为例&#xff0c;分别下载“RVC1006Nvidia”和…

C++的stack和Queue

1.简单实现stack 构建一个模板&#xff0c;俩个参数&#xff0c;这里第一个一般是数据的类型&#xff0c;第二个是由什么来实现栈&#xff0c;在主函数里传了int和vector<int>&#xff0c;第二个不传参也可以&#xff0c;因为是缺省参数&#xff0c;默认为vector&#x…