【算法笔记】动态规划--划分动态规划问题
【矩阵连乘问题】
输入：<A1,A 2,...,An>, Ai是矩阵
输出：计算A1 A2 ... An的最小代价方法
若A是p *q矩阵，B是q *r矩阵，则A *B的代价是O(pqr)
1.如何用子问题表示
dp[ i ][ j ]表示从 Ai 乘到 Aj 的最小代价方法
总问题表示为dp[ 1 ][ n ]
\2. 优化子结构和重叠子问题
\3. 递归方程式
dp[ i ][ j ] = min{ dp[ i ][ k ] + dp[ k+1 ][ j ] + w(Vi-1 Vk Vj)}
w(Vi-1 Vk Vj)指矩阵Ai~k * Ak+1~j的代价
递归终点：dp[ i ][ i ] = 0;
4.伪代码
5.时间复杂度分析：O（n^3）
【多边形的三角剖分问题】
与矩阵链乘问题几乎完全一致