记忆化搜索和动态规划 --最长回文子串为例
记忆化搜索
记忆化搜索是一种优化递归算法的方法,通过将已经计算过的子问题的结果存储起来(通常使用哈希表或数组),避免重复计算相同的子问题。
本质上是通过缓存中间结果来减少计算的重复性。
动态规划
动态规划是通过将问题分解成子问题来解决的,它通常通过表格化的方式(自底向上)来存储子问题的解,以便在需要时能够快速访问。
动态规划的核心思想是通过自底向上的方式来解决问题,通常使用一个数组或表格来存储每个子问题的解,从而避免了递归的重复计算。
二者区别与联系
记忆化搜索和动态规划的区别,主要在于计算的顺序。
记忆化搜索通常是自顶向下的递归方式,在递归中检查子问题是否已经计算过,并存储结果。
动态规划通常是自底向上的方式,逐步计算所有子问题,并存储所有的中间结果,最终得到问题的解。
两者的时间复杂度是相同的,都是 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);}};
由于函数调用的原因,使用递归的记忆化搜索算法的时间会稍微久一点
相关文章:
记忆化搜索和动态规划 --最长回文子串为例
记忆化搜索 记忆化搜索是一种优化递归算法的方法,通过将已经计算过的子问题的结果存储起来(通常使用哈希表或数组),避免重复计算相同的子问题。 本质上是通过缓存中间结果来减少计算的重复性。 动态规划 动态规划是通过将问题分…...
Tree Compass( Codeforces Round 934 (Div. 2) )
Tree Compass( Codeforces Round 934 (Div. 2) ) 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 掩码数组:缺失值处理的优雅方案 目录 #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可选。规定数组元素之间放置的内容。默认是 ""(空字符串)。array必需。要组合为字符串的数组。 技术细节 返回值:返回一个由数组元素组合成的字符串。PHP 版…...
react中如何获取dom元素
实现代码 const inputRef useRef(null) inputRef.current.focus()...
【C++】继承(下)
大家好,我是苏貝,本篇博客带大家了解C的继承(下),如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 5.继承与友元6.继承与静态成员7.复杂的菱形继承及菱形虚拟继承8.继…...
C语言实现字符串排序:从代码到原理深度解析
在编程的世界里,字符串处理是一项基础且重要的技能。今天,我们通过分析一段C语言代码来深入了解如何对字符串进行排序。 一、代码呈现 #include <stdio.h> #include <string.h> int main() { char s[1001]; scanf("%s", s); int…...
Vue3的el-table-column下拉输入实时查询API数据选择的实现方法
由于本人对el-table-column有下拉输入选择的要求,根据网上搜索的资料及本人优化,推出我比较满意的方法,供各位读者参考使用。 效果图 el-table-column写法 <el-table-columnlabel"货品编号"align"center"prop"…...
【数据结构】_链表经典算法OJ:复杂链表的复制
目录 1. 题目链接及描述 2. 解题思路 3. 程序 1. 题目链接及描述 题目链接:138. 随机链表的复制 - 力扣(LeetCode) 题目描述: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,…...
Vue 图片引用方式详解:静态资源与动态路径访问
目录 前言1. 引用 public/ 目录2. assets/ 目录3. 远程服务器4. Vue Router 动态访问5. 总结6. 扩展(图片不显示) 前言 🤟 找工作,来万码优才:👉 #小程序://万码优才/r6rqmzDaXpYkJZF 在 Vue 开发中&#x…...
chatGPT写的网页版贪吃蛇小游戏
chatGPT写的网页版贪吃蛇小游戏 前言网页版贪吃蛇小游戏 前言 之前无聊,让ChatGPT写了一段基于html语言的贪吃蛇小游戏代码 网页版贪吃蛇小游戏 将以下内容复制到记事本,重命名为xxx.html即可打开浏览器游玩 这里是一个使用HTML、CSS和JavaScript编写…...
Python量化交易助手:xtquant的安装与应用
Python量化交易助手:xtquant的安装与应用 技术背景和应用场景 在量化交易领域,Python因其强大的库支持和灵活性成为了许多开发者的首选语言。其中,xtquant 是迅投官方开发的一个Python包,专门用于与miniqmt通信,实现…...
前缀和算法
文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览 题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串 参考博主的讲解 思路分析:就是得使用前缀和记录情况,dp[i][j]表示s[0] 到s[i] 中&…...
Qt常用控件 输入类控件
文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1,录入用户信息1.4 例子2,正则验证手机号1.5 例子3,验证输入的密码1.6 例子4,显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1,获取输入框的内容2.4 例…...
《最小阻力之路》关于愿景的理解和思考
一、愿景的形成机制 1. 愿景的三层来源 来源层级形成机制案例潜在偏差风险① 本能冲动层对快感/痛苦的即时反应"想暴富"源于缺钱焦虑易被短期情绪劫持② 社会镜像层内化外界标准(家庭/社会/文化)"必须考研"因家人期待混淆他人需求…...
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 初始化步骤(各个节点都需执行)1.2.1 主机名与IP地址解析1.…...
虚幻基础17:动画层接口
能帮到你的话,就给个赞吧 😘 文章目录 animation layer interface animation layer interface 动画层接口:动画图表的集。仅有名字。 添加到动画蓝图中,由动画蓝图实现动画图表。...
无人机PX4飞控 | PX4源码添加自定义uORB消息并保存到日志
PX4源码添加自定义uORB消息并保存到日志 0 前言 PX4的内部通信机制主要依赖于uORB(Micro Object Request Broker),这是一种跨进程的通信机制,一种轻量级的中间件,用于在PX4飞控系统的各个模块之间进行高效的数据交换…...
HTMLCSS :下雪了
这段代码创建了一个动态的雪花飘落加载动画,通过 CSS 技术实现了雪花的下落和消失效果,为页面添加了视觉吸引力和动态感。 大家复制代码时,可能会因格式转换出现错乱,导致样式失效。建议先少量复制代码进行测试,若未能…...
如何处理 Typecho Joe 主题被抄袭或盗版的问题
在开源社区中,版权保护是一个非常重要的话题。如果你发现自己的主题(如 Joe 主题)被其他主题(如子比主题)抄袭或盗版,你可以采取以下措施来维护自己的权益。 一、确认侵权行为 在采取任何行动之前…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
