算法概论笔记 - 动态规划法

定义一组子问题，按照由小到大，以小问题的解答支持大问题求解的模式，依次解决所有的子问题，并最终得到原问题的解答。

隐含思想

DAG有向无圈图的拓扑排序

节点对应于我们定义的子问题，边表示子问题间的依赖关系：即如果求解子问题B必须依赖子问题A的解答，则（概念上）存在一条由A到B的边。

子问题性质
存在子问题间的一种排序以及如下的关联关系：对于任意一个 子问题，这种关联关系说明了如何在给定（在排序中）相对其“较小”的子问题的解的前提下，求得该子问题的解

妙处
恰当地选择子问题，使得所有重要的信息都得以保存并便于今后使用

常见子问题模式

模式1

输入为x1, x2, ..., xn，子问题为x1, x2, ..., xi。

最终子问题数量将为线性。

模式2

输入为x1, x2, ..., xn和y1, y2, ..., ym，子问题为x1, x2, ..., xi和y1, y2, ..., yj。

最终子问题数量为O(m*n)

模式3

输入为x1, x2, ..., xn，子问题为xi, x(i+1), ..., xj。

最终子问题数量为O(n^2)。

模式4

输入为树，子问题为其子树。

若树有n个节点，则最终子问题数量为O(nlogn)。

最长递增子序列

输入：一个数字序列a1、a2、...、an。

输出：从以上序列中按顺序选出的一个子集，并且严格单调递增，形如a(i1)、a(i2)、a(ik)，其中1<=i1<i2<...<ik<=n。

策略1

1. 为每个元素建立一个对应的节点，对任意两个存在递进关系的元素ai和ak（即同时满足i<j且ai<ak），增加一条连接两者对应节点的有向边(i, j)

2. 形成dag，求递增子序列问题变为寻找dag中的最长路径

for j = 1,2,...,n:
    L(j) = 1 + max{L(i):(i, j) in E}
return max{L(j)}

L(j)是以序列中j为终点的最长路径，即对应于最长递增子序列的长度

实现

1. 为方便图的邻接表表示，可变形为

for i = 1,2,...,n:
    for (i, j) in E:
    L(j) = max {L(j), L(i) + 1}
return max{L(j)}

see implement: dp.LongestIncreSub

2. 求反转图G的邻接表表示

此时无需构造原图G

时间复杂度max{O(n^2), O(V+E)}

策略2

子问题：将LCS(i)记做包含

如果一个树最优，那么其子树必然也最优

策略
假设我们需要计算

其中每个矩阵的维数分别为
定义 = the ; minimum ; cost ; of ; computing A_iA_{i+1}...A_j)
C(i, j)可分割为C(i, k)和C(k+1, j)两个子问题，即
 = min_{i<=k<j}[C(i,k) + C(k+1, j) + m_{i-1}m_km_j]​)

由于C(i, k)的维数为 ，C(k+1, j)的维数为

求解顺序：当求解到某个子问题时，比该子问题规模小的子问题已被求解。

因为(i,j)坐标并不在(i+1, j)坐标的下边或右边，此时无法按照从上至下，从左至右的求解顺序

for i = 1 to n: C(i, i) = 0
for s = 1 to n-1:
    for i = 1 to n-s:
        j = i+s
        C(i, j) = min{C(i,k) + C(k+1, j) + m(i-1)*m(k)*m(j):i<=k<j}
return C(1, n)

see implement: dp.MatrixChain

时间复杂度O(n^3)

动态规划 VS 递归记忆

记忆：递归算法记住之前的调用结果

• 优点：记忆只会求解那些实际被用到的子问题
• 缺点：递归所具有的的间接开销通常较高，其大O符号所包含的常数因子相对而言较大

写在最后

• 立个Flag，TODO will be done some day。
• 渣代码，且轻喷​:worried:​。