动态规划4：最长回文串（使用状态转移方程优化时间复杂度）

绝地灬酷狼 2023-07-10 05:07 69阅读 0赞

/* * 最长回文子串 * */
    #include <stdio.h>
    #include <cstring>
    
    const int maxn = 10010;
    char S[maxn];
    int dp[maxn][maxn]; //dp[i][j] 表示i到j表示的是不是回文串 1为是
    int ans = 1;//存放最长长度
    int main() { 
        fgets(S, maxn, stdin);
        int lengthS = strlen(S) - 1;
        //边界 dp[i][i]=1 dp[i][i+1]=(S[i]==S[j])?1:0
        for (int i = 0; i < lengthS; i++) { 
            dp[i][i] = 1;
            if (i + 1 < lengthS) { 
                if (S[i] == S[i + 1]) { 
                    dp[i][i + 1] = 1;
                    ans = 2;
                }
    
            }
        }
    
        //状态转移方程
        for (int L = 3; L <= lengthS; L++) { 
            //长度从3开始
            for (int i = 0; i + L - 1 < lengthS; i++) { 
                //控制左右端点
                int j = i + L - 1;//右端点
                if (S[i] == S[j] && dp[i + 1][j - 1] == 1) { 
                    dp[i][j] = 1;
                    ans = L;//更新长度
                }
            }
        }
        printf("%d", ans);
        return 0;
    
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202002291550464.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

[5. 最长回文子串][5.] 给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad"

痛定思痛。/ 2023年09月30日 21:27/ 0 赞/ 115 阅读

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

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

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

相关动态规划4：最长回文串（使用状态转移方程优化时间复杂度）

/ 最长回文子串 / include <stdio.h> include <cstring> const int maxn = 1

绝地灬酷狼/ 2023年07月10日 05:07/ 0 赞/ 70 阅读

相关 [数据结构与算法]最长回文子串(动态规划)

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad" 输出: "ba

快来打我*/ 2022年12月13日 12:49/ 0 赞/ 212 阅读

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

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

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

相关最长回文串

public String longestPalindrome(String s) { int start = 0, end = 0;

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 10:22/ 0 赞/ 286 阅读

相关动态规划---回文子串

1、题目： Given a string, your task is to count how many palindromic substrings in this str

末蓝、/ 2022年05月23日 07:57/ 0 赞/ 300 阅读

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

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

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

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

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

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