LCR 112. 矩阵中的最长递增路径【leetcode】/dfs+记忆化搜索

LCR 112. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。

示例 1:
在这里插入图片描述

输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4
解释:最长递增路径为 [1, 2, 6, 9]。

示例 2:
在这里插入图片描述

输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4
解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3:
输入:matrix = [[1]]
输出:1

提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

dfs+记忆化搜索

dp[i][j]表示以matrix[i][j]为出发点的最长递增路径

class Solution {
public:int res=0;int dp[205][205];int dfs(vector<vector<int>>& matrix,int m,int n,int x,int y){//如果dp[x][y]不为0,则表示已经有记录,直接返回长度if(dp[x][y]) return dp[x][y];if(x+1<m&&matrix[x+1][y]>matrix[x][y]) dp[x][y]=max(dp[x][y],dfs(matrix,m,n,x+1,y)+1);if(y+1<n&&matrix[x][y+1]>matrix[x][y]) dp[x][y]=max(dp[x][y],dfs(matrix,m,n,x,y+1)+1);if(x-1>=0&&matrix[x-1][y]>matrix[x][y]) dp[x][y]=max(dp[x][y],dfs(matrix,m,n,x-1,y)+1);if(y-1>=0&&matrix[x][y-1]>matrix[x][y]) dp[x][y]=max(dp[x][y],dfs(matrix,m,n,x,y-1)+1);return dp[x][y];}int longestIncreasingPath(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();//遍历每个点for(int i=0;i<m;i++){for(int j=0;j<n;j++){res=max(res,dfs(matrix,m,n,i,j));}}return res+1;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

前端覆盖率报告生成

前端精准测试是精准测试体系的一部分&#xff0c;但是由于前端项目比较灵活&#xff0c;各种框架&#xff0c;脚手架再加上开发同学写的不够规范&#xff0c;所以投入产出比较低&#xff0c;这部分内容在网上的资料也比较少。为了完善我们的精准测试体系&#xff0c;今年做了前…

21、状态模式(行为性模式)

版本一、get状态指针 #include <iostream> using namespace std;//前置声明 class Context;//状态 class State{ public://4个状态virtual void toUp (Context& context){ }virtual void toDown (Context& context){ }virtual void toLeft (Context& cont…

学习和认知的四个阶段,以及学习方法分享

本文分享学习的四个不同的阶段&#xff0c;以及分享个人的一些学习方法。 一、学习认知的四个阶段 我们在学习的过程中&#xff0c;总会经历这几个阶段&#xff1a; 第一阶段&#xff1a;不知道自己不知道&#xff1b; 第二阶段&#xff1a;知道自己不知道&#xff1b; 第三…

命名实体识别,根据实体计算准确率、召回率和F1

文章目录 简介数据格式介绍准确率、召回率和F1评估评估代码评估结果 进一步阅读参考 简介 使用大模型训练完命名实体识别的模型后&#xff0c;发现不知道怎么评估实体识别的准确率、召回率和F1。于是便自己实现了代码&#xff0c;同时提供了完整可运行的项目代码。 完整代码&…

SpringBoot快速入门(介绍,创建的3种方式,Web分析)

目录 一、SpringBoot介绍 二、SpringBootWeb快速入门 创建 定义请求处理类 运行测试 三、Web分析 一、SpringBoot介绍 我们可以打开Spring的官网(Spring | Home)&#xff0c;去看一下Spring的简介&#xff1a;Spring makes Java simple。 Spring发展到今天已经形成了一种…

学会Web UI框架--Bootstrap,快速搭建出漂亮的前端界面

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属的专栏&#xff1a;前端泛海 景天的主页&#xff1a;景天科技苑 文章目录 Bootstrap1.Bootstrap介绍2.简单使用3.布局容器4.Bootstrap实现轮播…

机器学习|KNN和Kmeans

KNN和Kmeans KNN KNN-K个最近的邻居&#xff0c;而K是可人先预设出来的。 所谓近朱者赤&#xff0c;近墨者黑。 可以选取离当前最近的K个样本来作为辅助判断&#xff0c;因为本样本和最近的K个样本应该是处于一种相似的状态。 以下是一个苹果和梨的识别任务。 图上会出现一个未…

011-keep-alive详解

keep-alive详解 1、简介2、keep-alive的使用效果未使用keep-alive的效果图使用keep-alive的效果图include和exclude指定是否缓存某些组件使用keep-alive的钩子函数执行顺序问题 3、keep-alive的应用场景举例4、总结 1、简介 keep-alive 是 Vue 的内置组件&#xff0c;当它包裹…

Elasticsearch架构原理

一. Elasticsearch架构原理 1、Elasticsearch的节点类型 在Elasticsearch主要分成两类节点&#xff0c;一类是Master&#xff0c;一类是DataNode。 1.1 Master节点 在Elasticsearch启动时&#xff0c;会选举出来一个Master节点。当某个节点启动后&#xff0c;然后使用Zen D…

理清关系简化LeetCode题库第3047题求交集区域内的最大正方形面积问题求解

3047. 求交集区域内的最大正方形面积 难度&#xff1a;中等 问题描述&#xff1a; 在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight&#xff0c;两个数组的大小都是 n x 2 &#xff0c;其中bottomLeft[i]和topRight[i]分别代表第i个…

爬虫(五)

1. 前端JS相关 三元运算 v1 条件 ? 值A : 值B; # 如果条件成立v1值A&#xff0c;不成立v1等于值Bres 1 1 ? 99 : 88 # res99特殊的逻辑运算 v1 11 || 22 # Ture v2 9 || 14 # 9 v3 0 || 15 # 15 v3 0 || 15 || "zhangfei" # 15赋值和…

Java二叉树 (2)

&#x1f435;本篇文章将对二叉树的一些基础操作进行梳理和讲解 一、操作简述 int size(Node root); // 获取树中节点的个数int getLeafNodeCount(Node root); // 获取叶子节点的个数int getKLevelNodeCount(Node root,int k); // 获取第K层节点的个数int getHeight(Node r…

【Claude3】利用Python中完成对Bedrock上的Claude的API调用

文章目录 1. 前期准备工作2. 安装和配置AWS CLI v23. 使用AWS configure命令配置AWS凭据4. 安装访问Bedrock的SDK5. 访问Amazon Bedrock UI6. 订阅Bedrock上的Claude模型7. 通过CLI命令列出所有可用的Claude模型8. 向Claude 3 Sonnet on Bedrock生成文本9. 参考链接 1. 前期准备…

云原生架构设计:分布式消息队列技术解析

消息队列是在消息传输过程中保存消息的容器&#xff0c;消息队列管理器在将消息从源到目标时充当中间人的角色&#xff0c;消息队列的主要目的是提供路由并保证消息的可靠传递。如果发送消息时接收者不可用&#xff0c;那消息队列就会保留消息&#xff0c;直到下次成功消费为止…

Excel 快速填充/输入内容

目录 一. Ctrl D/R 向下/右填充二. 批量输入内容 一. Ctrl D/R 向下/右填充 ⏹如下图所示&#xff0c;通过快捷键向下和向右填充数据 &#x1f914;当选中第一个单元格之后&#xff0c;可以按住Shift后&#xff0c;再选中最后一个单元格&#xff0c;可以选中第一个单元格和最…

CleanMyMac X4.14.7永久免费Mac电脑清理和优化软件

CleanMyMac X 是一款功能强大的 Mac 清理和优化软件&#xff0c;适合以下几类人群使用&#xff1a; 需要定期清理和优化 Mac 的用户&#xff1a;随着时间的推移&#xff0c;Mac 设备上可能会积累大量的无用文件、缓存和垃圾&#xff0c;导致系统运行缓慢。CleanMyMac X 的智能扫…

DataLoader

import torchvision from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriter# 准备的测试数据集 数据放在了CIFAR10文件夹下test_data torchvision.datasets.CIFAR10("./CIFAR10",trainFalse, transformtorchvision.transfor…

React useMemo钩子指南:优化计算性能

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【解读】OWASP大语言模型应用程序十大风险

OWASP大型语言模型应用程序前十名项目旨在教育开发人员、设计师、架构师、经理和组织在部署和管理大型语言模型&#xff08;LLM&#xff09;时的潜在安全风险。该项目提供了LLM应用程序中常见的十大最关键漏洞的列表&#xff0c;强调了它们的潜在影响、易利用性和在现实应用程序…

[Spring] IoC 控制反转和DI依赖注入和Spring中的实现以及常见面试题

目录 1. 什么是Spring 2.什么是IoC容器 3.通过实例来深入了解IoC容器的作用 3.1造一量可以定义车辆轮胎尺寸的车出现的问题 3.2解决方法 3.3IoC优势 4.DI介绍 5.Spring中的IoC和DI的实现 5.1.存对象 5.1.2 类注解 5.1.3 方法注解 5.2取对像 (依赖注入) 5.2.1.属性…