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

记忆化搜索和动态规划 --最长回文子串为例

记忆化搜索

记忆化搜索是一种优化递归算法的方法,通过将已经计算过的子问题的结果存储起来(通常使用哈希表或数组),避免重复计算相同的子问题。
本质上是通过缓存中间结果来减少计算的重复性。

动态规划

动态规划是通过将问题分解成子问题来解决的,它通常通过表格化的方式(自底向上)来存储子问题的解,以便在需要时能够快速访问。
动态规划的核心思想是通过自底向上的方式来解决问题,通常使用一个数组或表格来存储每个子问题的解,从而避免了递归的重复计算。

二者区别与联系

记忆化搜索和动态规划的区别,主要在于计算的顺序。
记忆化搜索通常是自顶向下的递归方式,在递归中检查子问题是否已经计算过,并存储结果。
动态规划通常是自底向上的方式,逐步计算所有子问题,并存储所有的中间结果,最终得到问题的解。
两者的时间复杂度是相同的,都是 O(n),因为两者都避免了重复计算子问题。

例题

最长回文子串 -力扣

记忆化搜索解答:

class Solution {
public:int dp[1000][1000];std::string ss;bool judge(int l, int r) {if (dp[l][r] != -1) {return dp[l][r];}if (ss[l] == ss[r]) {if (r - l > 1) {if (dp[l + 1][r - 1] == -1) {dp[l][r] = judge(l + 1, r - 1);} else {dp[l][r] = dp[l + 1][r - 1];}} else {dp[l][r] = 1;}} else {dp[l][r] = 0;}return dp[l][r];}std::string longestPalindrome(std::string s) {memset(dp,-1,sizeof(dp));int len = s.length();ss = s;int res = 0;int l = 0;for (int i = 0; i < len; i++) {for (int j = i; j < len; j++) {dp[i][j] = judge(i, j);if (dp[i][j] == 1 && j - i > res) {res = j - i;l = i;}}}return s.substr(l, res + 1);}
};

动态规划解答

class Solution {
public:std::string longestPalindrome(std::string s) {int len = s.length();bool dp[1000][1000];memset(dp,false,sizeof(dp));for(int i = len - 1; i >= 0; i--){for(int j = i; j < len; j++){if(s[i] != s[j]){dp[i][j] = false;}else{if(i == j){dp[i][j] = true;}else{if(j - i == 1){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}}}}int res = 0;int l = 0;for(int i = 0; i < len; i++){for(int j = i; j < len; j++){if(dp[i][j] == true){if(res < j - i){res = j - i;l = i;}}}}return s.substr(l,res + 1);}};

由于函数调用的原因,使用递归的记忆化搜索算法的时间会稍微久一点

相关文章:

记忆化搜索和动态规划 --最长回文子串为例

记忆化搜索 记忆化搜索是一种优化递归算法的方法&#xff0c;通过将已经计算过的子问题的结果存储起来&#xff08;通常使用哈希表或数组&#xff09;&#xff0c;避免重复计算相同的子问题。 本质上是通过缓存中间结果来减少计算的重复性。 动态规划 动态规划是通过将问题分…...

Tree Compass( Codeforces Round 934 (Div. 2) )

Tree Compass&#xff08; Codeforces Round 934 (Div. 2) &#xff09; You are given a tree with n n n vertices numbered 1 , 2 , … , n 1, 2, \ldots, n 1,2,…,n. Initially, all vertices are colored white. You can perform the following two-step operation: …...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.17 掩码数组:缺失值处理的优雅方案

2.17 掩码数组&#xff1a;缺失值处理的优雅方案 目录 #mermaid-svg-12vjJJbyudPnkYBO {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-12vjJJbyudPnkYBO .error-icon{fill:#552222;}#mermaid-svg-12vjJJbyudPnkYBO…...

PHP 常用函数2025.02

PHP implode() 函数 语法 implode(separator,array) 参数描述separator可选。规定数组元素之间放置的内容。默认是 ""&#xff08;空字符串&#xff09;。array必需。要组合为字符串的数组。 技术细节 返回值&#xff1a;返回一个由数组元素组合成的字符串。PHP 版…...

react中如何获取dom元素

实现代码 const inputRef useRef(null) inputRef.current.focus()...

【C++】继承(下)

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解C的继承&#xff08;下&#xff09;&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 5.继承与友元6.继承与静态成员7.复杂的菱形继承及菱形虚拟继承8.继…...

C语言实现字符串排序:从代码到原理深度解析

在编程的世界里&#xff0c;字符串处理是一项基础且重要的技能。今天&#xff0c;我们通过分析一段C语言代码来深入了解如何对字符串进行排序。 一、代码呈现 #include <stdio.h> #include <string.h> int main() { char s[1001]; scanf("%s", s); int…...

Vue3的el-table-column下拉输入实时查询API数据选择的实现方法

由于本人对el-table-column有下拉输入选择的要求&#xff0c;根据网上搜索的资料及本人优化&#xff0c;推出我比较满意的方法&#xff0c;供各位读者参考使用。 效果图 el-table-column写法 <el-table-columnlabel"货品编号"align"center"prop"…...

【数据结构】_链表经典算法OJ:复杂链表的复制

目录 1. 题目链接及描述 2. 解题思路 3. 程序 1. 题目链接及描述 题目链接&#xff1a;138. 随机链表的复制 - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;…...

Vue 图片引用方式详解:静态资源与动态路径访问

目录 前言1. 引用 public/ 目录2. assets/ 目录3. 远程服务器4. Vue Router 动态访问5. 总结6. 扩展&#xff08;图片不显示&#xff09; 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 在 Vue 开发中&#x…...

chatGPT写的网页版贪吃蛇小游戏

chatGPT写的网页版贪吃蛇小游戏 前言网页版贪吃蛇小游戏 前言 之前无聊&#xff0c;让ChatGPT写了一段基于html语言的贪吃蛇小游戏代码 网页版贪吃蛇小游戏 将以下内容复制到记事本&#xff0c;重命名为xxx.html即可打开浏览器游玩 这里是一个使用HTML、CSS和JavaScript编写…...

Python量化交易助手:xtquant的安装与应用

Python量化交易助手&#xff1a;xtquant的安装与应用 技术背景和应用场景 在量化交易领域&#xff0c;Python因其强大的库支持和灵活性成为了许多开发者的首选语言。其中&#xff0c;xtquant 是迅投官方开发的一个Python包&#xff0c;专门用于与miniqmt通信&#xff0c;实现…...

前缀和算法

文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览 题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串 参考博主的讲解 思路分析&#xff1a;就是得使用前缀和记录情况&#xff0c;dp[i][j]表示s[0] 到s[i] 中&…...

Qt常用控件 输入类控件

文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1&#xff0c;录入用户信息1.4 例子2&#xff0c;正则验证手机号1.5 例子3&#xff0c;验证输入的密码1.6 例子4&#xff0c;显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1&#xff0c;获取输入框的内容2.4 例…...

《最小阻力之路》关于愿景的理解和思考

一、愿景的形成机制 1. 愿景的三层来源 来源层级形成机制案例潜在偏差风险① 本能冲动层对快感/痛苦的即时反应"想暴富"源于缺钱焦虑易被短期情绪劫持② 社会镜像层内化外界标准&#xff08;家庭/社会/文化&#xff09;"必须考研"因家人期待混淆他人需求…...

Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群

Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群 简介Kubernetes 的工作流程概述Kubernetes v1.29.13 版本Ubuntu 22.04 系统安装部署 Kubernetes v1.29.13 集群 1 环境准备1.1 集群IP规划1.2 初始化步骤&#xff08;各个节点都需执行&#xff09;1.2.1 主机名与IP地址解析1.…...

虚幻基础17:动画层接口

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 animation layer interface animation layer interface 动画层接口&#xff1a;动画图表的集。仅有名字。 添加到动画蓝图中&#xff0c;由动画蓝图实现动画图表。...

无人机PX4飞控 | PX4源码添加自定义uORB消息并保存到日志

PX4源码添加自定义uORB消息并保存到日志 0 前言 PX4的内部通信机制主要依赖于uORB&#xff08;Micro Object Request Broker&#xff09;&#xff0c;这是一种跨进程的通信机制&#xff0c;一种轻量级的中间件&#xff0c;用于在PX4飞控系统的各个模块之间进行高效的数据交换…...

HTMLCSS :下雪了

这段代码创建了一个动态的雪花飘落加载动画&#xff0c;通过 CSS 技术实现了雪花的下落和消失效果&#xff0c;为页面添加了视觉吸引力和动态感。 大家复制代码时&#xff0c;可能会因格式转换出现错乱&#xff0c;导致样式失效。建议先少量复制代码进行测试&#xff0c;若未能…...

如何处理 Typecho Joe 主题被抄袭或盗版的问题

在开源社区中&#xff0c;版权保护是一个非常重要的话题。如果你发现自己的主题&#xff08;如 Joe 主题&#xff09;被其他主题&#xff08;如子比主题&#xff09;抄袭或盗版&#xff0c;你可以采取以下措施来维护自己的权益。 一、确认侵权行为 在采取任何行动之前&#xf…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...