动态规划（5）：最长回文字串

曾经终败给现在 2022-02-05 03:11 181阅读 0赞

## 题目 ##

给出一个字符串S, 求S 的最长回文子串（连续）的长度。

## 样例 ##

输入：PATZJUJZTACCBCC  
输出：9

## 题解 ##

**最优子结构**：如ATZJUJZTA是回文子串，那么它字串TZJUJZT一定是回文子串，且长度等于TZJUJZT的长度+2；

**重复子问题**：如求ATZJUJZTA和TZJUJZT的长度，都会用到JUJ的长度

**状态转移公式**：  
dp\[i\]\[j\] 表示从字符A\[i\]到A\[j\]的回文串长度，如果不是则为0  
初始值 0

边界：  
dp\[i\]\[i\] = 1  
dp\[i\]\[i + 1\] = (S\[i\] = S\[i + 1\])? 2: 0 。

公式  
dp\[i\]\[j\] = dp\[i + 1\]\[j - 1 \]+2, S\[i\]=S\[j\]

**最优解**:max(dp\[0\]\[0\]…dp\[n\]\[n\])

**时间复杂度**：O(n2)  
注意循环条件(串长从3到n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define N 100
    int main()
    { 
    	char A[N];
    	int dp[N][N];
    	gets(A);
    	int n=strlen(A),m=1;
    
    	for(int i=0;i<n;i++)
    	{ 
    		dp[i][i]=1;
            if(A[i]==A[i+1])
    		    dp[i][i+1]=2;
    	}
        for(int l=3;l<=n;l++)
            for(int i=0;i+l-1<n;i++)
            { 
    			int j=i+l-1;
    	 		if(A[i]==A[j] && dp[i+1][j-1]!=0)
                    dp[i][j]=dp[i+1][j-1]+2;
    				m=max(m,dp[i][j]);
            }
    	cout<<m;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]: /images/20220205/6d3dbf294fce428cbb0a9bf43dc048a4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No30】leetcode5. 最长回文子串

【算法|动态规划No30】leetcode5. 最长回文子串

傷城~/ 2024年04月27日 06:48/ 0 赞/ 38 阅读

相关 LeetCode_动态规划_中等_5.最长回文子串

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s =

我会带着你远行/ 2023年10月06日 18:09/ 0 赞/ 0 阅读

相关动态规划之最长回文子串

思路：这类问题通过穷举的办法，判断是否是回文子串并再筛选出最长的，效率很差。使用动态规划的策略来求解，首先从子问题入手，并将子问题的解保存起来，然后在求解后面的问题

傷城~/ 2023年08月17日 17:32/ 0 赞/ 83 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 232 阅读

相关最长回文字串 lintcode

package tju.chc; public class Solution { //方法1 暴力 /

浅浅的花香味﹌/ 2022年07月16日 08:00/ 0 赞/ 122 阅读

相关最长公共子串（动态规划）

描述：计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。输入：输入两个字符串输出：输出一个整数样

迷南。/ 2022年06月08日 10:07/ 0 赞/ 196 阅读

相关动态规划（5）：最长回文字串

题目给出一个字符串S, 求S 的最长回文子串（连续）的长度。样例输入：PATZJUJZTACCBCC 输出：9 题解最优子结构：如ATZJUJ

曾经终败给现在/ 2022年02月05日 03:11/ 0 赞/ 182 阅读

相关 [动态规划] 5. 最长回文子串

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。思路：用动态规划的方法，参考题解 ![watermark_typ

我会带着你远行/ 2021年11月27日 03:50/ 0 赞/ 310 阅读

相关最长回文字串算法，Manacher

转载：[Manacher算法（最大回文子串），JAVA实现][Manacher_JAVA] 转载于:https://www.cnblogs.com/push-blackpea

红太狼/ 2021年11月01日 07:44/ 0 赞/ 278 阅读

相关动态规划最长公共子串

核心思路和最长公共子序列一样区别在于子串必须连续可以先看我之前这篇文章 [最长公共子序列问题总结][Link 1] 最长公共子串同样是构造二维数组存储最大值，只不过去

我就是我/ 2021年08月11日 20:24/ 0 赞/ 372 阅读