添加最少的字符让字符串变为回文字符串（1）

#include <stdio.h>
#include <string.h>

#define MAXLEN 5001
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

int **getDP(char *str, int len);

void freeDP(int **dp, int len);

char *getPalStr(char *str, int len, int **dp);

int main(void) {
    int len, **dp;
    char str[MAXLEN], *res;
    scanf("%s", str);
    len = strlen(str);
    dp = getDP(str, len);
    res = getPalStr(str, len, dp);
    printf("%s\n", res);
    free(res);
    freeDP(dp, len);
    return 0;
}

int **getDP(char *str, int len) {
    int **dp = (int **) malloc(sizeof(int *) * len);
    for (int i = len - 1; i >= 0; i--) {
        dp[i] = (int *) malloc(sizeof(int) * len);
        dp[i][i] = 0;
        for (int j = i + 1; j < len; j++) {
            if (str[i] == str[j]) {
                dp[i][j] = j - i < 2 ? 0 : dp[i + 1][j - 1];
            } else {
                dp[i][j] = j - i < 2 ?
                    1 : (MIN(dp[i + 1][j], dp[i][j - 1]) + 1);
            }
        }
    }
    return dp;
}

void freeDP(int **dp, int len) {
    for (int i = 0; i < len; i++) {
        free(dp[i]);
    }
    free(dp);
}

char *getPalStr(char *str, int len, int **dp) {
    char *res = (char *) malloc(len + dp[0][len - 1] + 1);
    res[len + dp[0][len - 1]] = '\0';
    int l = 0, r = len + dp[0][len - 1] - 1;
    int i = 0, j = len - 1;
    while (i <= j) {
        if (str[i] == str[j]) {
            res[l++] = str[i++];
            res[r--] = str[j--];
            continue;
        }
        if (dp[i + 1][j] < dp[i][j - 1]) {
            res[l++] = str[i];
            res[r--] = str[i++];
        } else {
            res[l++] = str[j];
            res[r--] = str[j--];
        }
    }
    return res;
}