注意子串和子序列的區(qū)別
子串：必須連續(xù)
子序列：可以不連續(xù)
兩者都可以包含字符串本身

解法一：暴力求解

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

_Bool palindrome (char *str) {    //判斷一個(gè)字符串是否回文
    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) {    //計(jì)算回文子串個(gè)數(shù)
    int len = strlen(str);
    int count = 0;    //記錄回文子串個(gè)數(shù)
    for (int i = 0; i < len; i++)    //遍歷每一個(gè)子串
        for (int j = i; j < len; j++) {
            int n = 0;
            char *temp = (char *) malloc (sizeof(char) * (j - i + 2));    //拷貝遍歷過程中的每一個(gè)字符串
            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;
}

解法二：動(dòng)態(tài)規(guī)劃

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

int subPlalindromeNum (char *str, int len) {
    if (len == 0)
        return 0;
    int count = 0;    //記錄結(jié)果
    int **dp = (int **) malloc (sizeof(int *) * len);    //動(dòng)態(tài)分配二維 dp 數(shù)組并初始化為 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++) {    //第二個(gè)循環(huán)在遍歷第一個(gè)循環(huán)已經(jīng)遍歷過的字符，保證了 dp 數(shù)組的有效性
        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]) {    //首尾連續(xù)或者去掉首尾是回文，則計(jì)數(shù)
                    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;
}