动态规划实验_算法分析与设计

《动态规划实验_算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划实验实验二：在Σ={a,b,c}上定义乘法：abcabbabcbacacc若x=x1x2......xn是Σ上的乘法运算表达式。则x存在多少种可能的运算顺序，其结果均为a.动态规划算法所解问题的基本特征：1、最优子结构性质2、子问题重叠性质分析：Σ上的任意串x=x1x2......xn，有多少种可能的计算顺序使x=a.设子问题：xij=xixi+1...xkxk+1...xj,它有m[i][j][0]种不同的计算顺序，使得xij=am[i][j][1]种不同的计算顺序，使得xij=bm[i][j][2]种不同的计算顺序，使得

2、xij=c（其中[0]代表a,[1]代表b,[2]代表c）1xi=a&i=jm[i][j][0]=0xi!=a&i=j(k=i,j-1)Σ(m[i][k][0]*m[k+1][j][2]+m[i][k][1]*m[k+1][j][2]+m[i][k][2]*m[k+1][j][0])((k=i,j-1)Σ：“k=i”在Σ的下方，“j-1”在Σ的上方)packagedynamic_programming;importjava.io.BufferedReader;importjava.io.IOException;importjava.

3、io.InputStream;importjava.io.InputStreamReader;publicclassMultiplicationTable{privatestaticStringstr=null;publicstaticvoidmain(String[]args){InputStreaminputStream=System.in;InputStreamReaderinputStreamReader=newInputStreamReader(inputStream);BufferedReaderbufferedRead

4、er=newBufferedReader(inputStreamReader);try{out:while(true){System.out.print("Pleaseinputastring:");if((str=bufferedReader.readLine()).length()==0){System.out.println("EmptyInput!");continue;}for(charch:str.toCharArray()){if(ch>'c'

5、

6、ch<'a'){System.out.println("IllegalI

7、nput!inputamong'a','b'or'c'");continueout;}}break;}}catch(IOExceptione){e.printStackTrace();}intn=str.length();inta[][][]=newint[n][n][3];//intializethearrayfor(inti=0;i

8、i++)a[i][i][str.charAt(i)-'a']=1;//here0:a,1:b,2:cfor(ints=0;s

9、.println("");}//System.out.println("c啊啊啊啊啊");for(ints=0;s

10、intt=i;t