非科班菜鸡算法学习记录 | 代码随想录算法训练营第57天|| 647. 回文子串 516.最长回文子序列 动态规划总结篇


647. 回文子串

知识点:动规
状态:看思路自己写
思路:

dp不好想,dp[i][j] 是指左闭右闭时,是否为回文,bool类型;

注意递归公式和遍历顺序

class Solution {
public:int countSubstrings(string s) {int res=0;vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));//dp[i][j] 是指左闭右闭时,是否为回文,bool// s[i] != s[j] 时,肯定不是回文//相等时,三种情况,1. i和j也相等,回文 2. i和j差一,回文 3. 差的大于1,看dp[i+1][j-1]时候是回文for(int i = s.size() - 1 ;  0<=i; i-- ) {for(int j = i; j < s.size(); j++){if( s[i] == s[j]) {if( j - i <= 1) {res++;dp[i][j] = true;}else if( dp[i+1][j-1] ){res++;dp[i][j] = true;}}}}return res;}
};


516. 最长回文子序列

知识点:动规
状态:不会
思路:

dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]

在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。

如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

初始化:当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};

卡哥总结:

代码随想录 (programmercarl.com)

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

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

相关文章

音频——I2S TDM 模式(六)

I2S 基本概念飞利浦(I2S)标准模式左(MSB)对齐标准模式右(LSB)对齐标准模式DSP 模式TDM 模式 文章目录 TDM formatTDM format ATDM format BTDM format C总结 TDM format TDM 一般有三种常用操作模式&#xff1a;TDM A mode &#xff0c;TDM B mode 和 TDM C mode&#xff0c; …

【算法系列篇】模拟算法

文章目录 前言1.替换所有问号1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 提莫攻击2.1 题目要求2.2 做题思路2.3 Java代码实现 3. N 字形变换3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 外观数列4.1 题目要求4.2 做题思路4.3 Java代码实现 5. 数青蛙5.1 题目要求5.2 做题思…

安防监控/视频存储/视频汇聚平台EasyCVR如何接入智能分析网关V4?

TSINGSEE青犀AI边缘计算网关硬件 —— 智能分析网关目前有5个版本&#xff1a;V1、V2、V3、V4、V5&#xff0c;每个版本都能实现对监控视频的智能识别和分析&#xff0c;支持抓拍、记录、告警等&#xff0c;每个版本在算法模型及性能配置上略有不同。硬件可实现的AI检测包括&am…

VMware虚拟机安装CentOS7设置静态ip

vim /etc/sysconfig/network-scripts/ifcfg-ens33修改BOOTPROTO的值为static 增加最后那四项&#xff0c;参数在编辑&#xff0c;虚拟网络编辑器里面看

如何远程访问Linux MeterSphere一站式开源持续测试平台

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…

【算法专题突破】双指针 - 和为s的两个数字(6)

目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后&#xff1a; 1. 题目解析 题目链接&#xff1a;剑指 Offer 57. 和为s的两个数字 - 力扣&#xff08;Leetcode&#xff09; 这道题题目就一句话但是也是有信息可以提取的&#xff0c; 最重要的就是开始的那句话&#…

【LeetCode】19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点&#xff08;中等&#xff09; 方法&#xff1a;快慢指针 思路 为了找到倒数第 n 个节点&#xff0c;我们应该先找到最后一个节点&#xff0c;然后从它开始往前数 n-1 个节点就是要删除的节点。 对于一般情况&#xff1a;设置 fast 和 slow 两个…

Golang编写客户端SDK,并开源发布包到GitHub,供其他项目import使用

目录 编写客户端SDK&#xff0c;并开源发布包到GitHub1. 创建 GitHub 仓库2. 构建项目&#xff0c;编写代码Go 代码示例&#xff1a;项目目录结构展示&#xff1a; 3. 提交代码到 GitHub仓库4. 发布版本5. 现在其他人可以引用使用你的模块包了 编写客户端SDK&#xff0c;并开源…

个人博客项目测试报告

目录 一. 项目背景 二. 概述 三. 功能测试用例 四. 自动化测试用例 一. 项目背景 项目链接: http://81.70.189.104:8080/login.html 个人博客系统提供了 登录、注册、写博客&发布博客、删除博客、修改博客功能。前端的页面有 登录页、注册页、个人博客列表页、博客详情…

CloudCompare 二次开发(9)——半径滤波

目录 一、概述二、代码集成三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、概述 使用CloudCompare与PCL的混合编程实现点云半径滤波。半径滤波的算法原理见:PCL 半径滤波器。基于PCL将半径滤波集成到Cl…

c#事件(event)

概述&#xff1a; C#中的事件是一种特殊的委托&#xff0c;它用于实现观察者模式&#xff0c;允许对象在特定事件发生时通知其他对象。 以下是使用C#事件的示例&#xff1a; 首先&#xff0c;定义一个包含事件的类&#xff1a; public class EventPublisher {// 声明一个事…

通俗易懂讲解大模型:Tokenizer

Tokenizer Tokenizer 是 NLP pipeline 的核心组件之一。Tokenizer 的目标是&#xff1a;将文本转换为模型可以处理的数据。模型只能处理数字&#xff0c;因此 Tokenizer 需要将文本输入转换为数字输入。 通常而言有三种类型的 Tokenizer &#xff1a;Word-based Tokenizer、Cha…

PostgreSQL安装异常,服务无法启动导致创建服务器超时

win上安装pg后无法创建服务器&#xff0c;提示创建超时&#xff0c;发现服务列表里面pg15服务 并没有启动&#xff0c;启动服务器发现服务不了&#xff0c;截图忘记截了&#xff0c;复现不了&#xff0c;解决方法是 换个身份&#xff0c;然后继续启动&#xff0c;然后就可以在…

【每日运维】U盘启动盘安装 ESXi 6.7.0 安装卡在 loading /bnxtroce.v00

问题描述 ● ESXi 6.7.0 安装进度卡在loading /bnxtroce.v00 进度处 处理方法 ● 重新制作启动盘&#xff0c;写入方式改为&#xff1a;【USB-ZIPv2】 ● 设置服务器的 bios设置&#xff0c;启动方式改为【UEFI】 ● 重启开机安装即可

Playwright for Python:断言

一、支持的断言 Playwright支持以下几种断言&#xff1a; 断言描述expect(locator).to_be_checked()复选框被选中expect(locator).to_be_disabled()元素是禁用状态expect(locator).to_be_editable()元素是可编辑状态expect(locator).to_be_empty()容器是空的expect(locator).…

QT 发布软件基本操作

一、配置环境变量 找到Qt安装时的bin目录的路径&#xff1a;D:\Qt\Qt5.14.2\5.14.2\mingw73_64\bin&#xff0c;将目录拷贝至下述环境变量中。 打开计算机的高级系统设置 选中环境变量-->系统变量-->Path 点击编辑-->新建-->粘贴 二、生成发布软件的可执行程序 …

圆点和元素连线

效果图&#xff1a; 点上的线段跟踪元素移动&#xff0c;并且线会根据鼠标位置来连接元素的那个角 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><style>* {padding: 0;margin: 0;}.piont {width…

DP读书:鲲鹏处理器 架构与编程(十四)ACPI与软件架构具体调优

一分钟速通ACPI和鲲鹏软件移植 操作系统内核鲲鹏软件移植鲲鹏软件移植流程 编译工具选择编译参数移植案例源码修改案例鲲鹏分析扫描工具 Dependency Advisor鲲鹏代码迁移工具 Porting Advisor 鲲鹏软件性能调优鲲鹏软件性能调优流程CPU与内存子系统性能调优网络子系统性能调优磁…

库中是如何实现string类的?

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏1: &#x1f354;&#x1f35f;&#x1f32f;C语言初阶 &#x1f43b;推荐专栏2: &#x1f354;&#x1f35f;&#x1f32f;C语言进阶 &#x1f511;个人信条: &#x1f335;知行合一 &#x1f…

计及电池储能寿命损耗的微电网经济调度(matlab代码)

目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 该程序参考文献《考虑寿命损耗的微网电池储能容量优化配置》模型&#xff0c;以购售电成本、燃料成本和储能寿命损耗成本三者之和为目标函数&#xff0c;创新考虑储能寿命损耗约束、放电深度约束和储能循环次…