力扣——5.最长回文子串（c语言）

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2：

输入: "cbbd"
输出: "bb"

1、思路1：动态规划

对于一个子串而言，如果它是回文子串，并且长度大于2，那么将它首尾两个字母去掉以后，它仍然是个回文串。

那么我们就可以写出动态规划的状态转移方程：
$$
P(i,j) = P(i+1, j-1)&(S_i==S_j)
$$
也就是说，只有s[i+1 : j-1]是回文串，并且s的第i个字母和第j个字母相同时，s[i : j]才会是回文串。

以上所有的讨论是建立在子串长度大于2的前提上的，我们还要考虑动态规划的边界条件，即子串长度为1或2。对于长度为1的子串，它显然是个回文串；对于长度为2的子串，只要它的两个字母相同，它就是一个回文串。

因此，我们可以写出动态规划的边界条件：
$$
\begin{cases}
P(i,i) = true \
P(i,i+1) = (S_i == S_{i+1})
\end{cases}
$$
注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

代码如下：

char * longestPalindrome(char * s){
    int len = strlen(s);
    int dp[1000][1000];
    char result[10001] = {0};
    int l,i,j;
    for(l=0; l<len; ++l)
    {
        for(i=0; i+l<len; ++i)
        {
            j = i+l;
            if(0 == l){
                dp[i][j] = 1;
            } else if(1 == l){
                dp[i][j] = (s[i]==s[j]);
            } else{
                dp[i][j] = (s[i]==s[j] && dp[i+1][j-1]);
            }
            if(dp[i][j] && l+1>strlen(result)){
                strncpy(result, s+i, l+1);
                result[l+1] = '\0';
            }
        }
    }
    char *ret = result;
    return ret;
}