算法分析大作业14页.doc

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录1.动态规划解乘法表问题1.1问题描述-1.2算法设计思想-1.3设计方法-1.4源代码-1.5最终结果-2.动态规划解汽车加油行驶问题2.1问题描述-2.2算法设计思想-2.3设计方法-2.4源代码-2.5最终结果-3.总结1.动态规划解决乘法表问题1.1问题描述定义于字母表a,b,c)上的乘法表如表所示：依此乘法表,对任一定义于上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb)(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于上的字符串x=x1x2xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。1.2算法设计思想设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。