算法 矩阵最长递增路径-(递归回溯+动态规划)
牛客网: 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. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位…...
四、数学建模之图与网络模型
1.定义 2.例题及软件代码求解 一、定义 1.图和网络是相关概念 (1)图(Graph):图是数学和计算机科学中的一个抽象概念,它由一组节点(顶点)和连接这些节点的边组成。图可以是有向的&…...
php在header增加key,sign,timestamp,实现鉴权
在PHP中,您可以通过在HTTP请求的Header中增加Key、Sign和Timestamp等信息来进行安全性鉴权。 以下是一种基本的思路和示例,用于说明如何实现这种鉴权机制: 生成Key和Sign: 服务端和客户端之间共享一个密钥(Key&#x…...
Spring实例化源码解析之ConfigurationClassParser(三)
前言 上一章我们分析了ConfigurationClassPostProcessor的postProcessBeanDefinitionRegistry方法的源码逻辑,其中核心逻辑do while中调用parser.parse(candidates)方法,解析candidates中的候选配置类。然后本章我们主要分析ConfigurationClassParser的…...
在 Substance Painter中实现Unity Standard Shader
由于有需要在Substance Painter中显示什么样的效果,在Unity就要显示什么样的效果的需求,最近研究了几天,总算在Substance Painter中实现Unity standard的材质的渲染效果。具体效果如下: 在Unity中: Substance Painte…...
第二证券:个人开证券账户要开户费吗?
随着互联网和移动端东西的遍及,越来越多的人开端涉足股票投资,开立证券账户也成为一个热门话题。但是,许多初学者或许会有疑问,个人开证券账户是否需求支付开户费呢?这个问题的答案并不是那么简略,需求考虑…...
大厂面试-16道面试题
1 java集合类有哪些? List是有序的Collection,使用此接口能够精确的控制每个元素的插入位置,用户能根据索引访问List中元素。常用的实现List的类有LinkedList,ArrayList,Vector,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! …...
数据仓库介绍及应用场景
数据仓库(Data Warehouse)是一个用于存储、管理、检索和分析大量结构化数据的集中式数据库系统。与传统的事务处理数据库不同,数据仓库是为了支持决策支持系统(Decision Support Systems, DSS)和业务智能(B…...
代码随想录算法训练营Day56 | 动态规划(16/17) LeetCode 583. 两个字符串的删除操作 72. 编辑距离
动态规划马上来到尾声了,当时还觉得动态规划内容很多,但是也这么过来了。 第一题 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.介绍 资源链接 📚web前端期末大作业 (200套) 集合 Web前端期末大作业通常是一个综合性的项目,旨在检验学生在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稳定隧道(云端设置)3.3.Cpolar稳定隧道(本地设置) 4.公网访问测…...
uniapp瀑布流布局写法
首先我们要清楚瀑布流是什么? 瀑布流布局(Waterfall Flow Layout),也称为瀑布流式布局,是一种常见的网页或移动应用布局方式,特点是元素以不规则的方式排列,就像瀑布中的流水一样,每…...
蓝桥杯 题库 简单 每日十题 day8
01 扫雷 题目描述 在一个n行列的方格图上有一些位置有地雷,另外一些位置为空。 请为每个空位置标一个整数,表示周围八个相邻的方格中有多少个地雷。 输入描述 输入的第一行包含两个整数n,m。 第2行到第n1行每行包含m个整数,相邻整…...
Keepalived 高可用(附带配置实例,联动Nginx和LVS)
Keepalived 一、Keepalived相关知识点概述1.1 单服务的风险(单点故障问题)1.2 一个合格的集群应该具备的特性1.3 VRRP虚拟路由冗余协议1.4 健康检查1.5 ”脑裂“现象 二、Keepalived2.1 Keepalived是什么?2.2 Keepalived体系主要模块及其作用…...
第二证券:今年来港股回购金额超700亿港元 9月近200家公司获增持
本年以来,港股上市公司回购力度不断增强。据恒生指数公司计算,到9月15日,本年以来港股回购金额到达735亿港元,占去年全年总额的70%。该公司预测,2023年港股回购金额可能到达929亿港元,是前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工具
前言: 人工智能发布至今,过去了九个多月,已经成为了我们不管是工作还是生活中一个重要的辅助工具,大大提升了效率,作为一个人工智能的自然语言处理工具,它给各大行业的提供了一个巨大的生产工具,…...
《Python等级考试(1~6级)历届真题解析》专栏总目录
❤️ 专栏名称:《Python等级考试(1~6级)历届真题解析》 🌸 专栏介绍:中国电子学会《全国青少年软件编程等级考试》Python编程(1~6级)历届真题解析。 🚀 订阅专栏:订阅后可…...
在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,是根据《阿里巴巴java开发手册(黄山版)》转化而成的…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
表单设计器拖拽对象时添加属性
背景:因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...
