乘法表问题

定义于字母表∑{a,b,c)上的乘法表如表1所示

	a	b	c
a	b	b	a
b	c	b	a
c	a	c	c

 

依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为 i(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括 号方式,使由x导出的加括号表达式的值为a
要求：
     输入：输入一个以a,b,c组成的任意一个字符串。
     输出：计算出的加括号方式数。

 

算法思想：

结果a可拆为a*c,b*c,c*a.设dp[i][j][0]为字符串从i到j 结果为a的括号方式。

那么，dp[i][j][0]=∑(dp[i][m][0]*dp[m+1][j][2]//a*c

                         +dp[i][m][1]*dp[m+1][j][2]//b*c

                         +dp[i][m][2]*dp[m+1][j][0];//c*a)

(其中i<=m<j)

类比于求矩阵连乘最少计算量问题，我们可以确定其计算次序

因此可以得出如下代码：

#include "iostream"
using namespace std;
int map[3][3]={{1,1,0},{2,1,0},{0,2,2}};
int main()
{
	char c[10];
	int dp[10][10][3];
	int i=0,j,k;
	int b[10];
	while(scanf("%c",&c[i]),c[i++]!='\n')
	{
		b[i-1]=c[i-1]-97; //'a'对应0,'b'对应1,'c'对应2
	};
	int len=i-1;
	for (i=0;i<len;i++)
	{
		for (j=0;j<len;j++)
		{
			dp[i][j][0]=0;
			dp[i][j][1]=0;
			dp[i][j][2]=0;
			if (i==j)//初始化对角线上的元素
			{
				if (b[i]==0)
				{
					dp[i][j][0]=1;
				}
				if (b[i]==1)
				{
					dp[i][j][1]=1;
				}
				if (b[i]==2)
				{
					dp[i][j][2]=1;
				}
			}
		}
	}
	for (k=1;k<len;k++)
	{
		for (i=0;i<len-k;i++)
		{
			j=i+k;
			for (int m=i;m<j;m++)
			{
				int t=dp[i][m][0]*dp[m+1][j][2]+dp[i][m][1]*dp[m+1][j][2]+dp[i][m][2]*dp[m+1][j][0];
				dp[i][j][0]+=t;//max(dp[i][j][0],t);
				t=dp[i][m][0]*dp[m+1][j][0]+dp[i][m][0]*dp[m+1][j][1]+dp[i][m][1]*dp[m+1][j][1];
				dp[i][j][1]+=t;//max(dp[i][j][1],t);
				 t=dp[i][m][1]*dp[m+1][j][0]+dp[i][m][2]*dp[m+1][j][1]+dp[i][m][2]*dp[m+1][j][2];
				dp[i][j][2]+=t;//max(dp[i][j][2],t);
			}
			
		}
	}

	printf("%d\n",dp[0][len-1][0]);
	return 0;
}