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

算法 矩阵最长递增路径-(递归回溯+动态规划)

牛客网: BM61

求矩阵的最长递增路径

解题思路:

1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径
2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录
3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则对此位置赋值1,再对上下左右4个方向进行递归求解,每次递归后返回的最长路径需+1才是当前位置的最长路径,使用max选择最大值赋予dp[i][j],4个方向均遍历完后返回dp[i][j]给主程序。

代码:

// gopackage main
// import "fmt"/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** 递增路径的最大长度* @param matrix int整型二维数组 描述矩阵的每个数* @return int整型
*/
func max(x, y int) int {if x > y {return x} else {return y}
}
var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func process(matrix, dp [][]int, i, j, m, n int) int {if dp[i][j] > 0 {return dp[i][j]}dp[i][j] = 1for k := 0; k < 4; k++ {nexti := i + dirs[k][0]nextj := j + dirs[k][1]if nexti >= 0 && nexti < m && nextj >= 0 && nextj < n && matrix[nexti][nextj] < matrix[i][j] {dp[i][j] = max(dp[i][j], process(matrix, dp, nexti, nextj, m, n) + 1)}}return dp[i][j]
}func solve( matrix [][]int ) int {// write code hereif len(matrix) == 0 || len(matrix[0]) == 0 {return 0}m := len(matrix)n := len(matrix[0])dp := make([][]int, m)for i := 0; i < m; i++ {dp[i] = make([]int, n)}res := 0for i := 0; i < m; i++ {for j := 0; j < n; j++ {res = max(res, process(matrix, dp, i, j, m, n))}}return res
}

相关文章:

算法 矩阵最长递增路径-(递归回溯+动态规划)

牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置&#xff0c;max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时&#xff0c;使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时&#xff0c;如果dp[i][j]位…...

四、数学建模之图与网络模型

1.定义 2.例题及软件代码求解 一、定义 1.图和网络是相关概念 &#xff08;1&#xff09;图&#xff08;Graph&#xff09;&#xff1a;图是数学和计算机科学中的一个抽象概念&#xff0c;它由一组节点&#xff08;顶点&#xff09;和连接这些节点的边组成。图可以是有向的&…...

php在header增加key,sign,timestamp,实现鉴权

在PHP中&#xff0c;您可以通过在HTTP请求的Header中增加Key、Sign和Timestamp等信息来进行安全性鉴权。 以下是一种基本的思路和示例&#xff0c;用于说明如何实现这种鉴权机制&#xff1a; 生成Key和Sign&#xff1a; 服务端和客户端之间共享一个密钥&#xff08;Key&#x…...

Spring实例化源码解析之ConfigurationClassParser(三)

前言 上一章我们分析了ConfigurationClassPostProcessor的postProcessBeanDefinitionRegistry方法的源码逻辑&#xff0c;其中核心逻辑do while中调用parser.parse(candidates)方法&#xff0c;解析candidates中的候选配置类。然后本章我们主要分析ConfigurationClassParser的…...

在 Substance Painter中实现Unity Standard Shader

由于有需要在Substance Painter中显示什么样的效果&#xff0c;在Unity就要显示什么样的效果的需求&#xff0c;最近研究了几天&#xff0c;总算在Substance Painter中实现Unity standard的材质的渲染效果。具体效果如下&#xff1a; 在Unity中&#xff1a; Substance Painte…...

第二证券:个人开证券账户要开户费吗?

随着互联网和移动端东西的遍及&#xff0c;越来越多的人开端涉足股票投资&#xff0c;开立证券账户也成为一个热门话题。但是&#xff0c;许多初学者或许会有疑问&#xff0c;个人开证券账户是否需求支付开户费呢&#xff1f;这个问题的答案并不是那么简略&#xff0c;需求考虑…...

大厂面试-16道面试题

1 java集合类有哪些&#xff1f; List是有序的Collection&#xff0c;使用此接口能够精确的控制每个元素的插入位置&#xff0c;用户能根据索引访问List中元素。常用的实现List的类有LinkedList&#xff0c;ArrayList&#xff0c;Vector&#xff0c;Stack。 ArrayList是容量…...

搭建GraphQL服务

js版 GraphQL在 NodeJS 服务端中使用最多 安装graphql-yoga: npm install graphql-yoga 新建index.js: const {GraphQLServer} require("graphql-yoga")const server new GraphQLServer({ typeDefs: type Query { hello(name:String):String! …...

数据仓库介绍及应用场景

数据仓库&#xff08;Data Warehouse&#xff09;是一个用于存储、管理、检索和分析大量结构化数据的集中式数据库系统。与传统的事务处理数据库不同&#xff0c;数据仓库是为了支持决策支持系统&#xff08;Decision Support Systems, DSS&#xff09;和业务智能&#xff08;B…...

代码随想录算法训练营Day56 | 动态规划(16/17) LeetCode 583. 两个字符串的删除操作 72. 编辑距离

动态规划马上来到尾声了&#xff0c;当时还觉得动态规划内容很多&#xff0c;但是也这么过来了。 第一题 583. Delete Operation for Two Strings Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same. In on…...

HTML+CSS+JavaScript 大学生网页设计制作作业实例代码 200套静态响应式前端网页模板(全网最全,建议收藏)

目录 1.介绍2.这样的响应式页面这里有200套不同风格的 1.介绍 资源链接 &#x1f4da;web前端期末大作业 (200套) 集合 Web前端期末大作业通常是一个综合性的项目&#xff0c;旨在检验学生在HTML、CSS和JavaScript等前端技术方面的能力和理解。以下是一些可能的Web前端期末大…...

CFimagehost私人图床本地部署结合cpolar内网穿透实现公网访问

文章目录 1.前言2. CFImagehost网站搭建2.1 CFImagehost下载和安装2.2 CFImagehost网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 4.公网访问测…...

uniapp瀑布流布局写法

首先我们要清楚瀑布流是什么&#xff1f; 瀑布流布局&#xff08;Waterfall Flow Layout&#xff09;&#xff0c;也称为瀑布流式布局&#xff0c;是一种常见的网页或移动应用布局方式&#xff0c;特点是元素以不规则的方式排列&#xff0c;就像瀑布中的流水一样&#xff0c;每…...

蓝桥杯 题库 简单 每日十题 day8

01 扫雷 题目描述 在一个n行列的方格图上有一些位置有地雷&#xff0c;另外一些位置为空。 请为每个空位置标一个整数&#xff0c;表示周围八个相邻的方格中有多少个地雷。 输入描述 输入的第一行包含两个整数n&#xff0c;m。 第2行到第n1行每行包含m个整数&#xff0c;相邻整…...

Keepalived 高可用(附带配置实例,联动Nginx和LVS)

Keepalived 一、Keepalived相关知识点概述1.1 单服务的风险&#xff08;单点故障问题&#xff09;1.2 一个合格的集群应该具备的特性1.3 VRRP虚拟路由冗余协议1.4 健康检查1.5 ”脑裂“现象 二、Keepalived2.1 Keepalived是什么&#xff1f;2.2 Keepalived体系主要模块及其作用…...

第二证券:今年来港股回购金额超700亿港元 9月近200家公司获增持

本年以来&#xff0c;港股上市公司回购力度不断增强。据恒生指数公司计算&#xff0c;到9月15日&#xff0c;本年以来港股回购金额到达735亿港元&#xff0c;占去年全年总额的70%。该公司预测&#xff0c;2023年港股回购金额可能到达929亿港元&#xff0c;是前5年年度平均水平的…...

Autosar基础——RTE简介

AutoSAR文章目录 AUTomotive Open System Architecture Autosar-简介和历史发展 Autosar-软件架构 Autosar软件组件-Application Layer介绍和SWC(Software Component)类型 Autosar-Runnables(可运行实体) Autosar-OS配置 Autosar IOC机制(核间通信) Autosar实践-CANTp Auto…...

几个国内可用的强大的GPT工具

前言&#xff1a; 人工智能发布至今&#xff0c;过去了九个多月&#xff0c;已经成为了我们不管是工作还是生活中一个重要的辅助工具&#xff0c;大大提升了效率&#xff0c;作为一个人工智能的自然语言处理工具&#xff0c;它给各大行业的提供了一个巨大的生产工具&#xff0c…...

《Python等级考试(1~6级)历届真题解析》专栏总目录

❤️ 专栏名称&#xff1a;《Python等级考试&#xff08;1~6级&#xff09;历届真题解析》 &#x1f338; 专栏介绍&#xff1a;中国电子学会《全国青少年软件编程等级考试》Python编程&#xff08;1~6级&#xff09;历届真题解析。 &#x1f680; 订阅专栏&#xff1a;订阅后可…...

在IntelliJ IDEA 中安装阿里P3C以及使用指南

在IntelliJ IDEA 中安装阿里P3C以及使用指南 1.关于阿里p3c1.1说明1.2什么是P3C插件1.3p3c的作用是什么 2 如何在IDEA中安装p3c2.1 插件安装2.2 插件使用 3.参考连接 1.关于阿里p3c 1.1说明 代码规范检查插件P3C&#xff0c;是根据《阿里巴巴java开发手册(黄山版)》转化而成的…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...