数组维数为:dp[n][n][3];
dp[i][j][k] 表示 字符串xix(i+1)....xj的表达式的值为k(k>=0 k<=2,k=0表示a...) 的方式数；
递推式为：
dp[i][j][0]= sum(dp[i][i'][0]*dp[i'+1][j][2]+ dp[i][i'][1]*dp[i'+1][j][2]+dp[i][i'][2]*dp[i'+1][j][0])
dp[i][j][1]与dp[i][j][2]类似dp[i][j][0] 的求法
i'> =i and i' <j
#include <stdio.h>
#define MAX_LENGTH 256
void fun(int dp[][MAX_LENGTH][3],int n)
{
int i,j,k;
for(i=1;i<n;i++)
{
for(j=0;j+i<n;j++)
{
for(k=j;k<j+i;k++)
{
dp[j][j+i][0]+=dp[j][k][0]*dp[k+1][j+i][2]+dp[j][k][1]*dp[k+1][j+i][2]+dp[j][k][2]*dp[k+1][j+i][0];
dp[j][j+i][1]+=dp[j][k][0]*dp[k+1][j+i][0]+dp[j][k][0]*dp[k+1][j+i][1]+dp[j][k][1]*dp[k+1][j+i][1];
dp[j][j+i][2]+=dp[j][k][1]*dp[k+1][j+i][0]+dp[j][k][2]*dp[k+1][j+i][1]+dp[j][k][2]*dp[k+1][j+i][2];
}
}
}
}
int main()
{
int n;
char str[MAX_LENGTH];
int dp[MAX_LENGTH][MAX_LENGTH][3];
scanf("%s",&str);
n=0;
while (str[n]!='\0')
{
dp[n][n][str[n]-'a']=1;
n++;
}
fun(dp,n);
printf("%d\n",dp[0][n-1][0]);
return 0;
}