注意子串和子序列的区别
子串：必须连续
子序列：可以不连续
两者都可以包含字符串本身

解法一：暴力求解

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

_Bool palindrome (char *str) {    //判断一个字符串是否回文
    int tag = 1;
    for (int i = 0, len = strlen(str); i <= len / 2; i++) {
        if (str[i] != str[len - i - 1])
            tag = 0;
    }
    if (tag)
        return 1;
    else 
        return 0;
}

int subPalindromeNum (char *str) {    //计算回文子串个数
    int len = strlen(str);
    int count = 0;    //记录回文子串个数
    for (int i = 0; i < len; i++)    //遍历每一个子串
        for (int j = i; j < len; j++) {
            int n = 0;
            char *temp = (char *) malloc (sizeof(char) * (j - i + 2));    //拷贝遍历过程中的每一个字符串
            for (int k = i; k <= j; k++)
                temp[n++] = str[k];
            temp[n] = '\0';
            if (palindrome(temp))
                count++;
            free(temp);
        }
    return count;
}

int main() {
    for (char str[1000]; ~scanf("%s", &str);)
        printf("%d\n", subPalindromeNum(str));
    return 0;
}

解法二：动态规划

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

int subPlalindromeNum (char *str, int len) {
    if (len == 0)
        return 0;
    int count = 0;    //记录结果
    int **dp = (int **) malloc (sizeof(int *) * len);    //动态分配二维 dp 数组并初始化为 0
    for (int i = 0; i < len; i++) {
        dp[i] = (int *) malloc (sizeof(int) * len);
        for (int j = 0; j < len; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 0; i < len; i++) {    //第二个循环在遍历第一个循环已经遍历过的字符，保证了 dp 数组的有效性
        dp[i][i] = 1;
        count++;
        for (int j = i - 1; j >= 0; j--)
            if (str[i] == str[j])    //判断首尾是否相等
                if (i - 1 == j || dp[i - 1][j + 1]) {    //首尾连续或者去掉首尾是回文，则计数
                    dp[i][j] = 1;
                    count ++;
                }
    }
    free(dp);
    return count;
}

int main() {
    for (char str[10000]; ~scanf("%s", str);)
        printf("%d\n", subPlalindromeNum(str, strlen(str)));
    return 0;
}