DP

15.2 矩阵链乘法

给定n个矩阵的链，矩阵$A_i$的规模为$p_{i-1} \times p_i$，求完全括号化方案，使得计算$A_1A_2...A_n$所需标量乘法次数最少

1. 刻画最优解的结构特征，求解$A_iA_{i+1}...A_j$，为了对其括号化，就必须先在其中间$A_k$和$A_{k+1}$之前进行划分$i\le k \le j$，然后再分别计算$A_iA_{i+1}...A_k$和$A_{k+1}..A_j$
2. 递归求解方案，定义$m[i,j]$为$A_{i,j}$的最小乘法次数，则有$m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}p_kp_j$
3. 计算最优代价

matrix-chain-order(p)
    n = p.length - 1
    let m[1...n,1...n] be a new table
    for i = 1 to n
        m[i, i] = 0
    for l = 2 to n          // length of the chain
        for i = 1 to n - l + 1
            j = i + l - 1
            m[i, j] = inf
            for k = i to j-1
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
                m[i, j] = min(q, m[i, j])

---

15.4 最长公共子序列

给定两个序列$X=<x_1, x_2, ..., x_m>$和$Y=<y_1, y_2, ..., y_n>$求X和Y长度最长的公共子序列(不连续出现)

c[i, j]表示X前i位和Y前j位的LCS长度，则有

$$c[i,j]=\left\{ \begin{array}{rcl} 0 & i=0/j = 0\\ c[i-1,j-1]+1 & i,j>0,x_i=y_j \\ max(c[i,j-1],c[i-1,j]) & i,j>0, x_i \neq y_j \end{array} \right.$$