动态规划：矩阵连乘问题，字节跳动今日学习内容_c语言动态规划 递归 解决矩阵连乘问题

分析：

二.问题分析

由于矩阵乘法满足结合律，所以计算矩阵连乘的连乘积可以与许多不同的计算计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，那么可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积可递归地定义为：

（1）.单个矩阵是完全加括号的；

（2）.矩阵连乘积A是完全加括号的，则A可以表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，及A=（BC）

举个例子，矩阵连乘积A1A2A3A4A5，可以有5种不同的完全加括号方式：

(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)

每一种完全加括号的方式对应一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切的关系，即与矩阵的行和列有关。

补充一下数学知识，矩阵A与矩阵B可乘的条件为矩阵A的列数等于矩阵B的行数，例如，若A是一个p_q的矩阵，B是一个q_r的矩阵，则其乘积C=AB是一个p*r的矩阵。

源码如下：

#include

#include

using namespace std;

#define max 255

int a[max],m[max][max];

int Getmin(int i,int j)

{

int min,n;

if(m[i]