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

算法实验二 矩阵最小路径和 LIS

算法实验课二

矩阵最小路径和

leetcode裸题

最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例 1:

img

输入: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最长上升子序列

image-20240402221428416

image-20240402221459580

题目练习

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.合唱队形

image-20240402221625696

代码:

#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 &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例 1&#xff1a; 输入&…...

Apache Paimon实时数据糊介绍

Apache Paimon 是一种湖格式,可以使用 Flink 和 Spark 构建实时 数据糊 架构,用于流式和批处理操作。Paimon 创新地将湖格式和 LSM(日志结构合并树)结构相结合,将实时流式更新引入湖架构中。 Paimon 提供以下核心功能: 实时更新: 主键表支持大规模更新的写入,具有非常…...

计算机网络:数据链路层 - 可靠传输协议

计算机网络&#xff1a;数据链路层 - 可靠传输协议 可靠传输概念停止-等待协议 SW回退N帧协议 GBN选择重传协议 SR 可靠传输概念 如下所示&#xff0c;帧在传输过程中受到干扰&#xff0c;产生了误码。接收方的数据链路层&#xff0c;通过真伪中的真检验序列 FCS 字段的值&…...

苍穹外卖07(缓存菜品,SpringCache,缓存套餐,添加购物车菜品和套餐多下单,查看购物车,清除购物车,删除购物车中一个商品)

目录 一、缓存菜品 1 问题说明 2 实现思路 3 代码开发&#xff1a;修改DishServiceImpl 4 功能测试 二、SpringCache 1. 介绍 2. 使用语法 1 起步依赖 2 使用要求 3 常用注解 4 SpEL表达式(了解备用) 5 步骤小结 3.入门案例 1 准备环境 2 使用入门 1 引导类上加…...

C语言第三十八弹---编译和链接

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 编译和链接 1、翻译环境和运行环境 2、翻译环境 2.1、预处理&#xff08;预编译&#xff09; 2.2、编译 2.2.1、词法分析 2.2.2、语法分析 2.2.3、语义分…...

无人售货奶柜:开启便捷生活的新篇章

无人售货奶柜&#xff1a;开启便捷生活的新篇章 在这个快节奏的现代生活中&#xff0c;科技的革新不仅为我们带来了前所未有的便利&#xff0c;更在不经意间改变着我们的日常。其中&#xff0c;无人售货技术的出现&#xff0c;尤其是无人售货奶柜&#xff0c;已经成为我们生活…...

STM32为什么不能跑Linux?

STM32是一系列基于ARM Cortex-M微控制器的产品&#xff0c;它们主要用于嵌入式系统中。而Linux则是一个开源的类Unix操作系统&#xff0c;主要面向的是桌面电脑、服务器等资源丰富的计算机。虽然理论上可以将Linux移植到STM32上运行&#xff0c;但是由于两者之间存在着很多技术…...

Dubbo 3.x源码(18)—Dubbo服务引用源码(1)

基于Dubbo 3.1&#xff0c;详细介绍了Dubbo服务的发布与引用的源码。 此前我们学习了Dubbo的服务导出的源码&#xff0c;在DubboBootstrapApplicationListener#startSync方法中&#xff0c;在调用了exportServices方法进行服务导出之后&#xff0c;立即调用了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&#xff08;单文件组件&#xff09;由 3 个不同的实体组成&#xff1a;模板、脚本和样式。三者都很重要&#xff0c;但后者往往被忽视&#xff0c;即使它可能变得复杂&#xff0c;且经常导致挫折和 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 年企业存储市场报告发布

近日&#xff0c;IDC 发布了 2023 年度的中国存储市场报告。根据该报告&#xff0c;在 2023 年软件定义存储的市场占比进一步扩大&#xff0c;分布式全闪的增长尤其亮眼&#xff0c;其市场份额从 2022 年的 7% 剧增到 2023 年的 17.7%&#xff0c;增长了 152%。 01 中国企业存…...

LeetCode 707. 设计链表(单链表、(非循环)双链表 模板)

你可以选择使用单链表或者双链表&#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性&#xff1a;val 和 next 。val 是当前节点的值&#xff0c;next 是指向下一个节点的指针/引用。 如果是双向链表&#xff0c;则还需要属性 prev 以指示链表中的上一个节点…...

深入了解Flutter中Overlay的介绍以及使用

Flutter Overlay 介绍 在 Flutter 中&#xff0c;Overlay 是一种特殊的 Widget&#xff0c;它可以用来在应用程序的其他部分之上显示内容。Overlay 非常适合用于显示模态对话框、弹出菜单、工具提示等。 Overlay 的工作原理 Overlay 位于 Flutter 的渲染树之外&#xff0c;这…...

文本直接生成2分钟视频,即将开源模型StreamingT2V

Picsart人工智能研究所、德克萨斯大学和SHI实验室的研究人员联合推出了StreamingT2V视频模型。通过文本就能直接生成2分钟、1分钟等不同时间&#xff0c;动作一致、连贯、没有卡顿的高质量视频。 虽然StreamingT2V在视频质量、多元化等还无法与Sora媲美&#xff0c;但在高速运…...

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测 目录 时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测&#xff08;完整源码…...

FPGA高端图像处理开发板-->鲲叔4EV:12G-SDI、4K HDMI2.0、MIPI等接口谁敢与我争锋?

目录 前言鲲叔4EV----高端FPGA图像处理开发板核心板描述底板描述配套例程源码描述配套服务描述开发板测试视频演示开发板获取 前言 在CSDN写博客传播FPGA开发经验已经一年多了&#xff0c;帮助了不少人&#xff0c;也得罪了不少人&#xff0c;有的人用我的代码赢得了某些比赛、…...

linux练习-交互式传参

在shell脚本中&#xff0c;read 向用户显示一行文本并接受用户输入 #!/bin/bash read -p 依次输入你的姓名、年龄、家乡 name age home echo 我是$name,年龄$age,我来自$home...

【数据结构(一)】初识数据结构

❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进…...

亚马逊卖家公开信息数据提取:反爬攻防战与 Python 批量采集实战

摘要&#xff1a; 批量获取亚马逊&#xff08;Amazon&#xff09;第三方卖家的商业名称、信用代码和注册地址等信息&#xff0c;对于跨境 B2B 拓客和供应链分析具有重要意义。然而&#xff0c;亚马逊的 Cloudflare 盾和 Robot 验证码构成了极高的反爬门槛。本文将深度解析亚马逊…...

别再死记硬背Payload了!我用XSS-Game靶场,带你拆解18种过滤规则背后的绕过逻辑

从XSS-Game靶场实战中掌握18种过滤规则的逆向思维在网络安全领域&#xff0c;跨站脚本攻击&#xff08;XSS&#xff09;始终是Web应用面临的主要威胁之一。许多开发者虽然了解XSS的基本概念&#xff0c;但当面对各种复杂的过滤规则时&#xff0c;往往不知如何系统分析并构造有效…...

一次搞懂内存取证:用Volatility3和Cobalt Strike分析工具复现VNCTF‘来一把紧张刺激的CS’

实战内存取证&#xff1a;从Volatility3到Cobalt Strike信标分析全解析 在网络安全事件响应中&#xff0c;内存取证往往是发现高级威胁的最后一道防线。当攻击者使用文件无落地的技术时&#xff0c;传统的磁盘取证可能一无所获&#xff0c;而内存中却保留着攻击行为的完整痕迹。…...

使用TaotokenCLI工具一键配置开发环境中的API密钥

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 使用Taotoken CLI工具一键配置开发环境中的API密钥 在团队协作或个人开发中&#xff0c;为每个项目或成员手动配置大模型API密钥和…...

电子商务设计师软考备战:特别篇 - 综合模拟与备考策略

1. 考试形式与内容结构1.1 考试基本信息考试科目与时间基础知识考试&#xff1a;上午9:00-11:30&#xff08;150分钟&#xff09;应用技术考试&#xff1a;下午2:00-4:30&#xff08;150分钟&#xff09;题型与分值分布上午考试&#xff08;基础知识&#xff09;&#xff1a; -…...

可解释AI新突破:基于局部帕累托最优的模型解释框架

1. 项目概述&#xff1a;当AI模型成为“黑箱”&#xff0c;我们如何撬开它&#xff1f;在机器学习项目里摸爬滚打十几年&#xff0c;我见过太多这样的场景&#xff1a;团队花大力气训练出一个准确率高达95%的复杂模型&#xff08;比如深度神经网络&#xff09;&#xff0c;业务…...

从零到上机:我的第一个Quest 3空间锚点应用是如何跑起来的(附完整Unity工程)

从零到上机&#xff1a;我的第一个Quest 3空间锚点应用是如何跑起来的&#xff08;附完整Unity工程&#xff09;第一次戴上Meta Quest 3时&#xff0c;那种虚拟与现实交织的震撼感至今难忘。但作为开发者&#xff0c;更让我着迷的是如何让虚拟物体在真实空间中"记住"…...

Driver Store Explorer终极指南:轻松管理Windows驱动存储区,释放宝贵磁盘空间

Driver Store Explorer终极指南&#xff1a;轻松管理Windows驱动存储区&#xff0c;释放宝贵磁盘空间 【免费下载链接】DriverStoreExplorer Driver Store Explorer 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 你是否曾为Windows系统越来越慢而烦…...

GEP协议深度解读:AI智能体自我进化的基因工程

OpenAI 官宣全面支持MCP协议,标志着AI应用架构的"连接标准"已定。如果说MCP是AI时代的USB-C,解决了模型与工具的连接问题,那么GEP(Genome Evolution Protocol,基因组进化协议)则正在解决另一个更本质的问题——智能体的自我进化与生命周期管理。 作为下一代AI基…...

3分钟快速解决Windows热键冲突检测难题:Hotkey Detective终极指南

3分钟快速解决Windows热键冲突检测难题&#xff1a;Hotkey Detective终极指南 【免费下载链接】hotkey-detective A small program for investigating stolen key combinations under Windows 7 and later. 项目地址: https://gitcode.com/gh_mirrors/ho/hotkey-detective …...