动态规划乘法表问题

本文主要是介绍动态规划乘法表问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划乘法表问题
问题描述：
定义于字母表∑{a,b,c)上的乘法表如表1所示
表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的情况数，并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组a[n][n][3],n为输入字符串的长度，a[i][j][0]为从字符串中第i个元素到第j个元素的子串表达式值为a的加括号方式数，a[i][j][1]为从字符串中第i个元素到第j个元素的子串表达式值为b的加括号方式数，a[i][j][2]为从字符串中第i个元素到第j个元素的子串表达式值为c的加括号方式数。
由乘法表的定义则可知啊a[i][j][0]=（对k求和，k从i到j-1）a[i][k][0]*a[i][k+1][2]+a[i][k][1]*a[i][k+1][2]+a[i][k][2]*a[i][k+1][1];
同理可得到a[i][j][1]和a[i][j][2]。
同时由上面的表达式可知，要计算a[i][j][],需先计算a[i][k][]和a[i][k+1][]，这里k从i到j-1，故a[i][j][]可采取如下的计算次序
这里写图片描述
需要注意的是数越界问题。

#include <iostream>
#include <stdio.h>
using namespace std;
#define len 10
int main()
{char str[len];int a[len][len][3];char b[len];int i=0,j,k,t,size;while(i<len&&getchar(str[i])!='\n'){cin>>str[i];i++;}size=i;for(i=0; i<size; i++){for(j=0; j<size; j++){for(k=0; k<3; k++){a[i][j][k]=0;//初始化aij为0}}a[i][i][str[i]-'a']=1;//初始化一个长度的aij等于其字符，即a[i][i][0]=‘a’=1}for(k=1; k<size; k++){for(i=0; i<size; i++){if(i+k<len&&str[i+k]!='\0')j=i+k;elsej=size;//j的大小不能超过字符的长度cout<<"j="<<j<<endl;for(t=i; t<j; t++){a[i][j][0]+=a[i][t][0]*a[t+1][j][2]+a[i][t][1]*a[t+1][j][2]+a[i][t][2]*a[t+1][j][0];a[i][j][1]+=a[i][t][0]*a[t+1][j][0]+a[i][t][0]*a[t+1][j][1]+a[i][t][1]*a[t+1][j][1];a[i][j][2]+=a[i][t][1]*a[t+1][j][0]+a[i][t][2]*a[t+1][j][1]+a[i][t][2]*a[t+1][j][2];}}}cout<<a[0][size-1][0]<<endl;return 0;
}