当前位置: 首页 > 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…...

Keil环境下C与汇编混合编程实战:从参数传递到函数调用

1. 为什么需要C与汇编混合编程&#xff1f; 在嵌入式开发领域&#xff0c;C语言因其可移植性和开发效率成为主流选择&#xff0c;但当你需要精确控制硬件时序或优化关键代码段时&#xff0c;汇编语言的优势就显现出来了。我曾在电机控制项目中遇到一个典型场景&#xff1a;用C语…...

OpenClaw+GLM-4.7-Flash:自动化代码审查

OpenClawGLM-4.7-Flash&#xff1a;自动化代码审查 1. 为什么需要自动化代码审查 作为一个独立开发者&#xff0c;我经常面临一个尴尬局面&#xff1a;在深夜写完代码后直接提交&#xff0c;第二天醒来发现代码中存在明显的逻辑漏洞或风格问题。传统解决方案要么依赖昂贵的Sa…...

嵌入式LED控制库:裸机/RTOS下的确定性状态管理

1. 项目概述"FonctionLED" 是一个面向嵌入式微控制器的轻量级 LED 控制函数库&#xff0c;其设计目标并非提供图形化界面或高级动画引擎&#xff0c;而是聚焦于底层硬件操作的可靠性、可预测性与最小资源占用。从项目标题&#xff08;法语“LED功能”&#xff09;和摘…...

Jenkins与GitHub集成指南:从凭据配置到自动化构建的全流程

Jenkins与GitHub深度集成实战&#xff1a;构建企业级自动化流水线 在DevOps实践中&#xff0c;持续集成与持续交付(CI/CD)已成为现代软件开发的核心环节。Jenkins作为最流行的开源自动化服务器&#xff0c;与GitHub的深度集成能够显著提升团队协作效率。本文将带您从零开始构建…...

MS5803-14BA I²C驱动开发:嵌入式压力传感器实战指南

1. MS5803-14BA压力传感器库深度解析&#xff1a;面向嵌入式工程师的IC驱动开发实践1.1 传感器核心特性与工程定位MS5803-14BA是TE Connectivity&#xff08;原Measurement Specialties&#xff09;推出的高精度数字压力/温度复合传感器&#xff0c;采用MEMS压阻式传感原理与Δ…...

零基础快速入门前端CSS Transform 与动画核心知识点及蓝桥杯 Web 应用开发考点解析(可用于备赛蓝桥杯Web应用开发)

CSS 中的 transform&#xff08;变换&#xff09;和 animation&#xff08;动画&#xff09;是实现网页动态效果的核心工具&#xff0c;也是蓝桥杯 Web 应用开发赛道的高频考点一、CSS 2D 变换&#xff08;transform&#xff09;transform 用于对元素进行平移、旋转、缩放、倾斜…...

智慧城市中的时空AI:从路网数据到拥堵预测的完整项目拆解

智慧城市中的时空AI&#xff1a;从路网数据到拥堵预测的完整项目拆解 在省会城市早高峰的主干道上&#xff0c;交通信号灯与车流形成一场看不见的博弈。传统基于固定配时的信号控制系统&#xff0c;往往在突发拥堵面前显得力不从心。而某市"交通大脑"的落地案例显示&…...

如何快速创建专业图表:Mermaid数据可视化的完整指南

如何快速创建专业图表&#xff1a;Mermaid数据可视化的完整指南 【免费下载链接】mermaid mermaid-js/mermaid: 是一个用于生成图表和流程图的 Markdown 渲染器&#xff0c;支持多种图表类型和丰富的样式。适合对 Markdown、图表和流程图以及想要使用 Markdown 绘制图表和流程图…...

OpenClaw+GLM-4.7-Flash:个人博客自动更新系统搭建

OpenClawGLM-4.7-Flash&#xff1a;个人博客自动更新系统搭建 1. 为什么需要自动化博客维护 作为一个技术博主&#xff0c;我每周至少要花3-4小时在博客维护上&#xff1a;构思主题、撰写内容、调整格式、发布更新。最痛苦的不是写作本身&#xff0c;而是那些重复性的机械工作…...

Swagger2配置避坑指南:为什么你的Docket分组设置会导致api-docs 404?

Swagger2配置避坑指南&#xff1a;为什么你的Docket分组设置会导致api-docs 404&#xff1f; 在RESTful API开发中&#xff0c;Swagger2作为API文档生成工具被广泛使用。但许多开发者在配置过程中都遇到过这样的问题&#xff1a;明明能正常访问swagger-ui.html页面&#xff0c;…...