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

曾经终败给现在 2022-02-05 03:11 208阅读 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 条评论，208人围观）

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

相关阅读

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

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

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

相关力扣算法动态规划#5最长回文字串

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: “babad” 输出: “bab” 注意:

本是古典何须时尚/ 2023年10月11日 11:54/ 0 赞/ 34 阅读

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

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

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

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

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

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

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

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

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

相关最长回文字串 lintcode

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

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

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

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

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

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

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

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

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

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

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

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

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

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