2024/4/3-力扣-最长回溯子串-解 1：动态编程-回溯子串

char* longestPalindrome(char *s) {
    int n = strlen(s);
    if (s == NULL || n == 0 || n == 1) {
        return s;
    }
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    for (int i = n - 1; i >= 0; i--) { // 从下到上
        for (int j = i; j < n; j++) { // 从左到右
            if (s[i] == s[j]) {
                if (j - i <= 1) { // 情况一 和 情况二
                    dp[i][j] = 1;
                } else if (dp[i + 1][j - 1]) { // 情况三
                    dp[i][j] = 1;
                }
            }
        }
    }
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (dp[i][j] && j - i > r - l) {
                l = i;
                r = j;
            }
        }
    }
    int len = r - l + 1;
    char *res = malloc(sizeof(int) * len);
    int k = 0;
    for (int i = l; i <= r; i++) {
        res[k++] = s[i];
    }
    res[k] = '\0';
    return res;
}