算法实验二 矩阵最小路径和 LIS
算法实验课二
矩阵最小路径和
leetcode裸题
最小路径和
给定一个包含非负整数的 *m* x *n*
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]] 输出:12
提示:
-
m == grid.length
-
n == grid[i].length
-
1 <= m, n <= 200
-
0 <= grid[i][j] <= 200
class Solution {
public://dp[i][j]代表该位置上的最小和//dp[i][j] = dp[i-1][j]) if(grid[i-1][j] > )int minPathSum(vector<vector<int>>& grid) {int m = grid.size();//行数int n = grid[0].size();//列数
vector<vector<int>> dp = grid;for(int i = 1; i < m; i ++)dp[i][0] = dp[i][0] + dp[i - 1][0];for(int j = 1; j < n; j ++)dp[0][j] = dp[0][j] + dp[0][j - 1];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]) + dp[i][j];// dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}
return dp[m - 1][n - 1];}
};
完整实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
LL dp[N][N];
LL grid[N][N];
int n, m;
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++){cin >> grid[i][j];dp[i][j] = grid[i][j];//初始化}for(int i = 1; i <= n; i ++)dp[i][1] = dp[i][1] + dp[i - 1][0];for(int j = 1; j <= m; j ++)dp[1][j] = dp[1][j] + dp[1][j - 1];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){dp[i][j] += min(dp[i - 1][j], dp[i][j - 1]);}}cout << dp[n][m] << endl;return 0;
}
LIS最长上升子序列
题目练习
1.蓝桥勇士
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N];//表示以a[i]结尾的最长上升子序列的长度
int a[N];
int n;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];dp[i] = 1;//初始化}for(int i = 1; i <= n; i ++)for(int j = 1; j < i; j ++)if(a[j] < a[i])dp[i] = max(dp[i], dp[j] + 1);//状态转移方程
int res = -0x3f3f3f3f;//答案初始为一个最小值for(int i = 1; i <= n; i ++)//判断以哪个a[i]结尾是最长的上升子序列res = max(res, dp[i]);cout << res << endl;return 0;
}
判断以哪个a[i]结尾是最长的上升子序列可以偷懒使用库函数
// int res = -0x3f3f3f3f;//答案初始为一个最小值 // for(int i = 1; i <= n; i ++)//判断以哪个a[i]结尾是最长的上升子序列 // res = max(res, dp[i]);
cout << *max_element(dp + 1, dp + 1 + n) << endl;
以上最长上升子序列(LIS)算法时间复杂度O(n^2)
还有一种实现方式,可以利用二分实现O(nlogn)的时间复杂度
题目二
1.合唱队形
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N], dp1[N], dp2[N], n;
int main()
{cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];dp1[i] = 1;dp2[i] = 1;}
for(int i = 1; i <= n; i ++)for(int j = 1; j < i; j ++)if(a[j] < a[i])dp1[i] = max(dp1[i], dp1[j] + 1);for(int i = n; i ; i --)for(int j = n; j > i; j --)if(a[j] < a[i])dp2[i] = max(dp2[i], dp2[j] + 1);int res = -0x3f3f3f3f;for(int i = 1; i <= n; i ++)res = max(res, dp1[i] + dp2[i] - 1);cout << n - res << endl;return 0;
}
leetcode裸题
300. 最长递增子序列 - 力扣(LeetCode)
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int dp[2550];if(nums.size() == 0)return 0;for(int i = 0; i < nums.size(); i ++){dp[i] = 1;//初始化for(int j = 0; j < i; j ++)if(nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);}
return *max_element(dp, dp + nums.size());
}
};
相关文章:
算法实验二 矩阵最小路径和 LIS
算法实验课二 矩阵最小路径和 leetcode裸题 最小路径和 给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 1: 输入&…...
Apache Paimon实时数据糊介绍
Apache Paimon 是一种湖格式,可以使用 Flink 和 Spark 构建实时 数据糊 架构,用于流式和批处理操作。Paimon 创新地将湖格式和 LSM(日志结构合并树)结构相结合,将实时流式更新引入湖架构中。 Paimon 提供以下核心功能: 实时更新: 主键表支持大规模更新的写入,具有非常…...
计算机网络:数据链路层 - 可靠传输协议
计算机网络:数据链路层 - 可靠传输协议 可靠传输概念停止-等待协议 SW回退N帧协议 GBN选择重传协议 SR 可靠传输概念 如下所示,帧在传输过程中受到干扰,产生了误码。接收方的数据链路层,通过真伪中的真检验序列 FCS 字段的值&…...
苍穹外卖07(缓存菜品,SpringCache,缓存套餐,添加购物车菜品和套餐多下单,查看购物车,清除购物车,删除购物车中一个商品)
目录 一、缓存菜品 1 问题说明 2 实现思路 3 代码开发:修改DishServiceImpl 4 功能测试 二、SpringCache 1. 介绍 2. 使用语法 1 起步依赖 2 使用要求 3 常用注解 4 SpEL表达式(了解备用) 5 步骤小结 3.入门案例 1 准备环境 2 使用入门 1 引导类上加…...
C语言第三十八弹---编译和链接
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】 编译和链接 1、翻译环境和运行环境 2、翻译环境 2.1、预处理(预编译) 2.2、编译 2.2.1、词法分析 2.2.2、语法分析 2.2.3、语义分…...
无人售货奶柜:开启便捷生活的新篇章
无人售货奶柜:开启便捷生活的新篇章 在这个快节奏的现代生活中,科技的革新不仅为我们带来了前所未有的便利,更在不经意间改变着我们的日常。其中,无人售货技术的出现,尤其是无人售货奶柜,已经成为我们生活…...
STM32为什么不能跑Linux?
STM32是一系列基于ARM Cortex-M微控制器的产品,它们主要用于嵌入式系统中。而Linux则是一个开源的类Unix操作系统,主要面向的是桌面电脑、服务器等资源丰富的计算机。虽然理论上可以将Linux移植到STM32上运行,但是由于两者之间存在着很多技术…...
Dubbo 3.x源码(18)—Dubbo服务引用源码(1)
基于Dubbo 3.1,详细介绍了Dubbo服务的发布与引用的源码。 此前我们学习了Dubbo的服务导出的源码,在DubboBootstrapApplicationListener#startSync方法中,在调用了exportServices方法进行服务导出之后,立即调用了referServices方法…...
设计模式:工厂模式和抽象工厂模式的区别
定义 工厂模式(Factory Pattern)通常指的是工厂方法模式(Factory Method Pattern),它定义了一个创建对象的方法,由子类决定要实例化的类。工厂方法让类的实例化推迟到子类。 抽象工厂模式(Abstract Factory Pattern)提供了一个接口,用于创建相关或依赖对象的家族,而…...
python面试题(36~50)
36、如何取一个整数的绝对值? 这可以通过abs函数来实现。 abs(2) #> 2 abs(-2) #> 2 37、如何将两个列表组合成一个元组列表? 可以使用zip函数将列表组合成一个元组列表。这不仅仅限于使用两个列表。也适合3个或更多列表的情况。 a [a,b,c] b [1,2,3] [(k,v) fo…...
Vue 样式技巧总结与整理[中级局]
SFC(单文件组件)由 3 个不同的实体组成:模板、脚本和样式。三者都很重要,但后者往往被忽视,即使它可能变得复杂,且经常导致挫折和 bug。 更好的理解可以改善代码审查并减少调试时间。 这里有 7 个奇技淫巧…...
cesium加载.tif格式文件
最近项目中有需要直接加载三方给的后缀名tif格式的文件 <script src"https://cdn.jsdelivr.net/npm/geotiff"></script> 或者 yarn add geotiff npm install geotiff 新建tifs.js import GeoTIFF, { fromBlob, fromUrl, fromArrayBuffer } from geotif…...
分布式全闪占比剧增 152%,2023 年企业存储市场报告发布
近日,IDC 发布了 2023 年度的中国存储市场报告。根据该报告,在 2023 年软件定义存储的市场占比进一步扩大,分布式全闪的增长尤其亮眼,其市场份额从 2022 年的 7% 剧增到 2023 年的 17.7%,增长了 152%。 01 中国企业存…...
LeetCode 707. 设计链表(单链表、(非循环)双链表 模板)
你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点…...
深入了解Flutter中Overlay的介绍以及使用
Flutter Overlay 介绍 在 Flutter 中,Overlay 是一种特殊的 Widget,它可以用来在应用程序的其他部分之上显示内容。Overlay 非常适合用于显示模态对话框、弹出菜单、工具提示等。 Overlay 的工作原理 Overlay 位于 Flutter 的渲染树之外,这…...
文本直接生成2分钟视频,即将开源模型StreamingT2V
Picsart人工智能研究所、德克萨斯大学和SHI实验室的研究人员联合推出了StreamingT2V视频模型。通过文本就能直接生成2分钟、1分钟等不同时间,动作一致、连贯、没有卡顿的高质量视频。 虽然StreamingT2V在视频质量、多元化等还无法与Sora媲美,但在高速运…...
时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测
时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测 目录 时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测(完整源码…...
FPGA高端图像处理开发板-->鲲叔4EV:12G-SDI、4K HDMI2.0、MIPI等接口谁敢与我争锋?
目录 前言鲲叔4EV----高端FPGA图像处理开发板核心板描述底板描述配套例程源码描述配套服务描述开发板测试视频演示开发板获取 前言 在CSDN写博客传播FPGA开发经验已经一年多了,帮助了不少人,也得罪了不少人,有的人用我的代码赢得了某些比赛、…...
linux练习-交互式传参
在shell脚本中,read 向用户显示一行文本并接受用户输入 #!/bin/bash read -p 依次输入你的姓名、年龄、家乡 name age home echo 我是$name,年龄$age,我来自$home...
【数据结构(一)】初识数据结构
❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进…...
前端三剑客 —— CSS (第六节)
目录 内容回顾: 弹性布局属性介绍 案例演示 商品案例 布局分析 登录案例 网格布局 内容回顾: 变量:定义变量使用 --名称:值; 使用变量: 属性名:var(--名称)&a…...
MyBatis 解决上篇的参数绑定问题以及XML方式交互
前言 上文:MyBatis 初识简单操作-CSDN博客 上篇文章我们谈到的Spring中如何使用注解对Mysql进行交互 但是我们发现我们返回出来的数据明显有问题 我们发现后面三个字段的信息明显没有展示出来 下面我们来谈谈解决方案 解决方案 这里的原因本质上是因为mysql中和对象中的字段属性…...
Rust语言之属性宏(Attribute Macro)derive
文章目录 Rust语言之属性宏(Attribute Macro)derive Rust语言之属性宏(Attribute Macro)derive 属性宏是一种基于属性的宏,用于修改、扩展或注解 Rust 代码。它们通常用于为函数、结构体、枚举、模块等添加元数据或自…...
[技术闲聊]我对电路设计的理解(六)-原理图封装
电路设计的直观体现就是完整的原理图,绘制电路图阶段的第一步,绘制原理图封装库。 封装库一共有两种,一种是原理图封装库,一种是PCB封装库,如下图所示。 原理图封装和PCB封装之间的唯一关联就是 引脚位号,…...
算法(滑动窗口四)
1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words ["ab","cd","ef"]ÿ…...
学习记录:bazel和cmake运行终端指令
Bazel和CMake都是用于构建软件项目的工具,但它们之间有一些重要的区别和特点: Bazel: Bazel是由Google开发的构建和测试工具,用于构建大规模的软件项目。它采用一种称为“基于规则”的构建系统,它利用构建规则和依赖关…...
蓝桥杯刷题--python-37-分解质因数
3491. 完全平方数 - AcWing题库 nint(input()) res1 i2 while i*i<n: if n%i0: t0 while n%i0: n//i t1 if t%2: res*i i1 if n>1: res*n print(res) 4658. 质因数个数 - AcWing题库…...
Delphi编写的图片查看器
UNIT Unit17;INTERFACEUSESWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs,Vcl.StdCtrls, Vcl.ExtDlgs, Vcl.ExtCtrls, Vcl.Imaging.jpeg; //注意:要加入jpej 否侧浏览图…...
Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐
前言 最近在开发swing客户端时候碰到一个棘手的问题: Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐如果是vue或者react,一搜百度什么都出来了,swing的话,嗯。。。资料有点少而且大部分是stack overflow上面的…...
C# MES通信从入门到精通(8)——C#调用Webservice服务进行数据交互
前言 在上位机开发领域,使用webservice来访问客户的终端Mes系统是一项必备的技能,本文详细介绍了如何在c#中调用webservice服务,不仅介绍了使用添加服务引用直接调用webservice中的方法外还介绍了使用http的post方法调用webservice方法,过程详细且均为实战经验总结,对于初…...
购物平台网站建设流程/自动外链网址
自从上次发现了,object对象值为 null 时,if(object) false, 最近做资源兼容时,爱上这么写: _view[xxx] && (_view[xxx].visible false); 这个写法在fp11或fp9 里是没问题的,…...
做网站的机构/推广普通话手抄报图片
关于跨域问题 网上一般都是两种解决方案 1.通过实现接口 WebMvcConfigurer (拦截器的方式实现) 2.通过CorsFilter 实现 package com.take.takeDemo.Common.config;import org.springframework.context.annotation.Bean; import org.springframework.co…...
建设银行登录网站/seo网站技术培训
less与cat和more的区别: cat命令功能用于显示整个文件的内容单独使用没有翻页功能因此经常和more命令搭配使用,cat命令还有就是将数个文件合并成一个文件的功能。 more命令功能:让画面在显示满一页时暂停,此时可按空格健继续显示下…...
保险公司网站建设方案/seo点击排名
session会话保存会话的两种技术Session详解会话 会话:一个用户打开浏览器,浏览多个web页面之后,关闭浏览器。这个过程可以称之为会话。 有状态会话:用户浏览一个网站之后,下次再浏览时,这个网站知道他曾经…...
wordpress添加新浪微博/百度关键词排名突然消失了
播星联合创始人梁达的视频号:视商梁达今年微信悄然进军短视频领域,强势推出视频号。它带来的13亿用户基础的巨大流量,强大的社交关系链,无疑对短视频市场产生了巨大冲击,是对流量格局的重塑,可以说是当下最新的风口。今天播星给大家带来…...
做网站需要看什么书/小学生摘抄新闻2024
传送门 首先这玩意儿很明显是分数规划,二分一个答案\(mid\),边权变为\(w_i-mid\),然后看看能不能找到一条路径长度在\([L,R]\)之间,且边权总和非负,这个可以转化为求一条满足条件的边权最大的路径 这个实际上可以用点分…...