动态规划算法之矩阵连乘积问题2
程序员文章站
2022-07-03 14:40:51
...
在上篇文章当中,我们学习了矩阵的连乘积问题,并且得到了它的最少数乘次数矩阵和最佳断开位置矩阵,但是我们现在想直观的看到矩阵的加括号方式,不想在最佳断开位置矩阵里一个一个的对应去找,因此我们需要写一个更加直观的看到加括号方式的函数。
我们简单的分析一下(递归算法):
在s[1][n]的值我们知道A[1][n]最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n]),而此时,k=s[1][n]。同理可得A[1:s[1][n]]的最优加括号方式,此时i=1,j=s[1][n],k=s[i][j]=s[1][s[1][n]],代入有:(A[1:s[1][s[1][n]])(A[s[1][s[1][n]+1:s[1][n]],所以,我们就可以递推下去了。
代码如下:(代码来自于刘伟老师)
// 递归算法构造矩阵连乘积问题的最优解...
void AddMatrixChainBrackets( int i, int j, int **s )
{
if ( i == j )
return;
AddMatrixChainBrackets( i, s[ i ][ j ], s ); // A[ i : k ]
AddMatrixChainBrackets( s[ i ][ j ] + 1, j, s ); // A[ k + 1 : j ]
printf("乘积 A%d,%d", i, s[ i ][ j ] );
printf(" and A%d,%d\n", ( s[ i ][ j ] + 1 ), j );
}
我们用一个例题来演示一下,帮助大家更好的理解
运行结果如下:
这时我们就可以很明了的看到矩阵乘积的加括号方式(A(B(CD)))。
下一篇: 类加载器ClassLoader