动态规划2：算法考试矩阵连乘问题（超详细手写过程）-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划2：算法考试矩阵连乘问题（超详细手写过程）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

更多期末复习笔记欢迎访问我的博客：Miuuu · 语雀

动态规划理论基础：(6条消息) 动态规划1：动态规划的入门初学理论基础_黑色柳丁Angel的博客-CSDN博客

矩阵连乘问题是我在算法课接触的第一个动态规划问题，老师用了整整一节课介绍

问题描述：

给定n个矩阵{A1，A2，... ，An}，其中相邻的两个矩阵（Ai与Ai+1）是可乘的（i=1，2，... ，n-1）。考察这n个矩阵的连乘积（A1A2...An)。

由于矩阵乘法满足结合律，因此计算矩阵的连乘积可以有不同的计算次序。这种计算次序可以用加括号的方式来确定。

例如：矩阵连乘积 A1A2A3A4 可以有以下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矩阵，运算次数为：p*q*r

例题详解：

动态规划2：算法考试矩阵连乘问题（超详细手写过程）

动态规划2：算法考试矩阵连乘问题（超详细手写过程）文章来源地址https://www.toymoban.com/news/detail-402148.html

到了这里，关于动态规划2：算法考试矩阵连乘问题（超详细手写过程）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！