30-算法设计

4.6.2　算法设计

采用自底向上的方法求最优值，对于每一个小规模的子问题都求最优值，并记录最优策略（加括号位置），具体算法设计如下。

（1）确定合适的数据结构

采用一维数组p[]来记录矩阵的行和列，第i个矩阵的行数存储在数组的第i−1位置，列数存储在数组的第i位置。二维数组m[][]来存放各个子问题的最优值，二维数组s[][]来存放各个子问题的最优决策(加括号的位置)。

（2）初始化

采用一维数组p[]来记录矩阵的行和列，m[i][i]=0，s[i][i]=0，其中i= 1，2，3，…，n。

（3）循环阶段

• 按照递归关系式计算2个矩阵A _i、A _i+1相乘时的最优值，j=i+1，并将其存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，3，…，n−1。
• 按照递归关系式计算3个矩阵相乘A _i、A _i+1、A _i+2相乘时的最优值，j=i+2，并将其存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，3，…，n−2。
• 以此类推，直到求出n个矩阵相乘的最优值m[1][n]。

（4）构造最优解

根据最优决策信息数组s[][]递归构造最优解。s[1][n] 表示A₁A₂…A _n最优解的加括号位置，即（A₁A₂…A_s[1][n]）（A_s[1][n]+1…A _n），我们在递归构造两个子问题（A₁A₂…A_s[1][n]）、（A_s[1][n]+1…A _n）的最优解加括号位置，一直递归到子问题只包含一个矩阵为止。