动态规划（1）

动态规划（Dynamic Programming）是一种具有分治思想的迭代技术，它用于求解某些复杂的不包含决策过程的最优化问题，其基本思路是将原问题分解为子问题，并保存子问题的求解结果，从而避免不必要的重复计算。动态规划的主要思想就是将复杂的问题分解成一系列子问题，依次求解子问题，最后将子问题的结果组合起来，达到总体最优解的目的。

解决此类问题的重要思路：

1)  找到状态转移方程

2)  要确定好初始值

3）找到边界条件

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring

        下面我们来分析一下这题，如果字符串的长度为1，则就是最长字串，如果长度大于2的话要另外考虑。

我们定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示字符串从索引 i 到索引 j 的子串是否为回文子串。根据回文子串的定义，我们知道如果一个字符串是回文的，那么去掉它的首尾字符后仍然是回文的。

根据以上分析，我们可以得出以下状态转移方程：

dp[i][j]  =  (s[i] == s[j])  &&  ( dp[i + 1][j - 1] )

其中，dp[i + 1][j - 1] 表示字符串从索引 i + 1 到 j - 1 的子串是否为回文子串。

根据状态转移方程，我们需要从长度较短的子串开始计算，逐步扩展子串的长度，直到得到最终的结果。

具体的算法步骤如下：

1. 初始化一个二维数组 dp，将所有 dp[i][i]（长度为 1 的子串）都设为 true。
2. 初始化最长回文子串的长度 maxLen 和起始位置 start，初始值为 1 和 0。
3. 从长度为 2 的子串开始遍历，逐步增加子串的长度 L，遍历范围为 L = 2 到 L = len，其中 len 是字符串的长度。
4. 对于每个子串的起始位置 i，计算子串的结束位置 j，即 j = i + L - 1。若 s[i] 等于 s[j]，则根据状态转移方程计算 dp[i][j]，（在此处有个小细节，当i - j < 3时候并且s[i] = s[j],即子串只有两个字符，且这两个字符相等的时候，也是符合回文的要求)
5. 若 dp[i][j] 为 true，并且子串的长度 L 大于 maxLen，则更新 maxLen 和 start。
6. 最终，根据 maxLen 和 start 找到最长回文子串，并返回该子串。

具体的代码实现如下:

(c语言)

char* longestPalindrome(char* s) {
    int len = strlen(s);
    if (len < 2) {
        return s;
    }
    int dp[1000][1000];
    int maxLen = 1;
    int start = 0;  // 记录最长回文子串的起始位置

    // 先全部初始化，认为长度为 1 的都是回文子串
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
    }

    // 从小开始，长度 L 等于 2
    for (int L = 2; L <= len; L++) {
        // 从左边开始
        for (int i = 0; i < len; i++) {
            // 确定右边的边界 j - i + 1 = L
            int j = L + i - 1;
            if (j >= len) {
                break;
            }

            // 判断左右字符是否相等
            if (s[i] != s[j]) {
                dp[i][j] = 0;
            } else {
                //长度为2的回文串
                if (j - i < 3) {
                    dp[i][j] = 1;
                } else {
                    //转移方程
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            // 如果当前子串是回文且长度大于最长回文子串长度
            if (dp[i][j] == 1 && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }

    // 创建动态数组存储结果
    char* result = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(result, s + start, maxLen);
    result[maxLen] = '\0';

    return result;
}

(java语言)

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        // 根据起始位置和最大长度截取最长回文子串
        return s.substring(begin, begin + maxLen);
    }
}