【算法笔记】动态规划--划分动态规划问题

【矩阵连乘问题】

输入:<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.伪代码

img

5.时间复杂度分析:O(n^3)

【多边形的三角剖分问题】

与矩阵链乘问题几乎完全一致