LeetCode5.2-动态规划求解最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"

输出："bb"

示例 3：

输入：s = "a"

输出："a"

示例 4：

输入：s = "ac"

输出："a"

前边两篇文章分别使用中心扩展法、马拉车算法求解了最长回文子串，本文用动态规划解一下此题。不得不说动态规划解决此问题也是一个时间复杂度为O(n^2)的算法，只是通过这个问题感受一下动态规划的解题过程。

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.1-马拉车算法求解最长回文子串

先简单说一下思路，对于一个回文子串来说，假设长度大于2时，它的首尾一定相等，同时去掉首尾后还是回文子串。这就得到了状态转移方程，从文章（动态规划入门 ）可知，这是动态规划关键步骤一。

//DP关键步骤1：状态转移方程，s[strStart + 1][strEnd - 1]是回文子串
//且s[strStart] == s[strEnd]时，s[strStart][strEnd]才是回文子串
 {
       dp[strStart][strEnd] = (s[strStart] == s[strEnd] && dp[strStart + 1][strEnd - 1]);
 }

如果这个回文子串小于等于2，等于2或者等于1时；我们可以认为长度为1的子串，显然是回文子串；长度为2的子串，只要它的两个字母相同，则为回文子串。这就构成了边界条件。

if (strLen == 0)//边界条件1，长度为1的子串，显然是回文子串
 {
      dp[strStart][strEnd] = 1;
 }
 else if (strLen == 1)//边界条件2，长度为2的子串，只要它的两个字母相同，是回文子串
 {
      dp[strStart][strEnd] = (s[strStart] == s[strEnd]);
 }

动态规划关键步骤2，缓冲并复用以往结果。我们需要缓冲的内容是什么，一个二维数组dp[i][j]，该数组表示，以i开头，以j结尾的，长度为j - i + 1的子串是否为回文子串。

dp[i][j] = 0 该子串不是回文子串

dp[i][j] = 1 该子串是回文子串

举例我们的 字符串为 ovvolevel,求出它的最长回文子串。

dp数组中，对角线都为1，都是回文子串，长度为1，边界条件1。

dp[1][2] = 1 是回文子串，长度为2，指的是vv

dp[5][7] = 1 是回文子串，长度为3，指的是eve

dp[0][3] = 1 是回文子串，长度为4，指的是ovvo

dp[4][8] = 1 是回文子串，长度为5，指的是level

有了以往结果，我们就可以从中找出最长的回文子串作为结果就是dp[4][8] = 1，level。

我们判断dp[4][8] = 1且它的长度level为5比之前的更长，则更新。

 //如果有更长的回文子串则更新
            if (dp[strStart][strEnd] && strLen + 1 > strlen(retStr))
            {
                for (int m = strStart,n = 0; n < strLen + 1; m++,n++)
                {
                    retStr[n] = s[m];
                    printf("retStr[%d] = %c\n",n,retStr[n]);
                }
                retStr[strTatalLen + 1] = '\0';
            }

动态规划关键步骤三：

按照顺序从小往大算，从小往大时我们的变量表示什么，需要思考一下。我们遍历回文子串的长度从小到大。比如，ovvolevel这个字符串，长度为9，我们分别看它长度为0,1,2,3,4,5,6,7,8时的情况。

//DP关键步骤3：按照顺序从小往大算
    for (int strLen = 0; strLen < strTatalLen; strLen++)//回文子串的长度
    {

遍历结果如下：

回文子串长度为1，strLen = 0，边界条件1，长度为1的子串，显然是回文子串

dp[0][0] = 1 retStr[0] = o

dp[1][1] = 1

dp[2][2] = 1

dp[3][3] = 1

dp[4][4] = 1

dp[5][5] = 1

dp[6][6] = 1

dp[7][7] = 1

dp[8][8] = 1

回文子串长度为2，strLen = 1，边界条件2，长度为2的子串，只要它的两个字母相同，是回文子串

dp[0][1] = 0

dp[1][2] = 1 retStr[0] = v retStr[1] = v

dp[2][3] = 0

dp[3][4] = 0

dp[4][5] = 0

dp[5][6] = 0

dp[6][7] = 0

dp[7][8] = 0

回文子串长度为3

dp[0][2] = 0

dp[1][3] = 0

dp[2][4] = 0

dp[3][5] = 0

dp[4][6] = 0

dp[5][7] = 1 retStr[0] = e retStr[1] = v retStr[2] = e

dp[6][8] = 0

回文子串长度为4

dp[0][3] = 1 retStr[0] = o retStr[1] = v retStr[2] = v retStr[3] = o

dp[1][4] = 0

dp[2][5] = 0

dp[3][6] = 0

dp[4][7] = 0

dp[5][8] = 0

回文子串长度为5

dp[0][4] = 0

dp[1][5] = 0

dp[2][6] = 0

dp[3][7] = 0

dp[4][8] = 1 retStr[0] = l retStr[1] = e retStr[2] = v retStr[3] = e retStr[4] = l

回文子串长度为6

dp[0][5] = 0

dp[1][6] = 0

dp[2][7] = 0

dp[3][8] = 0

回文子串长度为7

dp[0][6] = 0

dp[1][7] = 0

dp[2][8] = 0

回文子串长度为8

dp[0][7] = 0

dp[1][8] = 0

回文子串长度为9

dp[0][8] = 0

动态规划关键三步都搞定，这个问题也就解决了。

完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char* longestPalindrome_dp(char* s)
{
    int strTatalLen = strlen(s);
    //定义并初始化二维数组
    //DP关键步骤2：缓冲并复用以往结果
    bool dp[strTatalLen][strTatalLen];
    for (int k = 0; k < strTatalLen; k++)
    {
        for (int q = 0; q < strTatalLen; q++)
        {
            dp[k][q] = 0;
        }  
    }
    //存储最终结果
    char* retStr = (char*)malloc(sizeof(int) * strTatalLen);
    memset(retStr, 0x00, sizeof(char) * strTatalLen);
    //DP关键步骤3：按照顺序从小往大算
    for (int strLen = 0; strLen < strTatalLen; strLen++)//回文子串的长度
    {
        for (int strStart = 0; strStart + strLen < strTatalLen; strStart++)
        {//回文子串的开始位置strStart,这样可以通过strEnd =  strStart + strLen得到子串的结束位置
            int strEnd = strStart + strLen;
            if (strLen == 0)//边界条件1，长度为1的子串，显然是回文子串
            {
                dp[strStart][strEnd] = 1;
            }
            else if (strLen == 1)//边界条件2，长度为2的子串，只要它的两个字母相同，是回文子串
            {
                dp[strStart][strEnd] = (s[strStart] == s[strEnd]);
            }
            else//DP关键步骤1：状态转移方程，s[strStart + 1][strEnd - 1]是回文子串
            //且s[strStart] == s[strEnd]时，s[strStart][strEnd]才是回文子串
            {
                dp[strStart][strEnd] = (s[strStart] == s[strEnd] && dp[strStart + 1][strEnd - 1]);
            }
           //如果有更长的回文子串则更新
            if (dp[strStart][strEnd] && strLen + 1 > strlen(retStr))
            {
                for (int m = strStart,n = 0; n < strLen + 1; m++,n++)
                {
                    retStr[n] = s[m];
                    printf("retStr[%d] = %c\n",n,retStr[n]);
                }
                retStr[strTatalLen + 1] = '\0';
            } 
        }   
    }
    return retStr;
}

int main()
{
    char s[] ="ovvolevel";
    char* s1 = longestPalindrome_dp(s);
    printf("%s\n", s1);
    
    return 0;
}

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.1-马拉车算法求解最长回文子串