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

绝地灬酷狼 2023-07-10 05:07 21阅读 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