jasperzhong
commented
3 years ago Chapter 15: Dynamic Programming
第一段就道清楚了DP和分治区别:
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. ("Programming" in this context refers to a tabular method, not to writing computer code.) As we saw in Chapter 2 and 4, divide-and-conquer algorithms partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming applies when the subproblems overlap - that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
确实. 比如最简单的斐波那契数列 f(n) = f(n-1) + f(n-2). 如果用分治(递归)的方法写, 会有大量的重复计算.
DP一般有几个步骤:
- 分析最优解的结构.
- 递归定义最优解的值
- 自底向上计算最优解的值
- 从计算结果中构建最优解（如果只需要最优解的值，可以忽略这一步）
Rod cutting
问题就是不同长度的钢棍价格不同，现给定一个钢棍，如何切钢棍是的利益最大.
这个问题是具有最优子结构(optimal substructure): optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently. (最优解是由其子问题的最优解构成的)
还有一种decomposition的方法: 切成两段，左边的固定不动，接下来只切右边的. 这样的equation是
这样就只有一个related的subproblem，而不是两个.
上面这个式子如果用递归(top-down)去求解，复杂度是O(2^n)...没错，因为切一个长度为n的棍子有2^{n-1}种方式(中间n-1个地方可以选择切或者不切).
如果用bottom-up的方式去求解，就变成O(n^2)了.
这是subproblem graph (n=4).
bottom-up的求解方式其实是"reverse topological sort". 而且时间复杂度一般和subproblem graph的vertices和edges数量成正比.
如何输出切分策略呢? 也就是DP的第四步. 可以用一个数组来记录每一个长度的钢棍的第一段的切割位置.
Array s记录了subproblem为j的时候，最优的切割位置为i. 输出结果就是一个切割过程.
### Matrix-chain multiplication
一串矩阵乘法，决定计算顺序（加括号）. 很经典的问题, 之前看过很多次.
首先这个问题的解空间是很大的，具体来说是卡特兰数. 很容易理解，最后结果是由两个subproblem的结果相乘得到，而如何划分这个subproblem在任意位置都可以.
用DP四步法分析这个问题:
- 是否具有最优子问题结构
A[i:j]问题的最优解，一定是A[i:k]最优，A[k:j]最优. 如果A[i:k]有更好的加括号方法，那就应该直接用，A[i:j]也可以受益. 所以矛盾.
- 最优解的递归结构
- 自底向上计算最优值
这其实构成是这一个三角形表格
比如l=2的时候，计算的是m[i, i+1]，其实就是倒数第二行 (1,2) (2,3), (3,4), (5,6). 以此类推. 最后得到最优解m[1, 6]. 时间复杂度为O(n^3).
- 构建最优解
妙啊
Elements of dynamic programming
讨论了什么时候使用DP. 使用DP有两个重要条件:
- 最优子结构(optimal substructure)
- 重叠子问题(overlapping subproblems)
最优子结构
如果最优解包含其子问题的最优解，那么就称该问题具有最优子结构的性质.
一般具有如下特征:
- 一个问题的解包含了做一个选择. 比如选择最初的切割位置(切钢棍)，或者是选择split matrix chain的位置.
- “cut-and-paste": 给定一个最优解，如果我们假设其子问题的解不是最优的，得出整个问题的解也不是最优的，从而矛盾.
不同的最优子结构区别表现在:
- 最优解包含多少个subproblems.
- 最优解需要做多少次选择去决定使用哪些subproblems.
比如rod-cutting问题中，最优解只用到了一个subproblem，但是要做n次选择来决定哪个将用于最优解. 而matrix-chain问题中，最优解用到了两个subproblems，需要j-i个choices.
DP算法的复杂度取决于:
- subproblems的数量——对应subproblem graph中的vertex
- 每次检查subproblem的选择数量——对应subproblem graph的edges
比如rod-cutting问题，subproblems数量是O(n)，而每个subproblem有O(n)个选择，所以总的复杂度是O(n^2). 而matrix-chain问题，subproblems数量是O(n^2)，每个subproblem有O(n)个选择，所以总的复杂度是O(n^3).
重叠子问题
应该是比较好理解的. 对比下和分治的区别.
Longest common subsequence
著名的最长公共子序列(LCS)问题. 问题描述是寻找一个最长的subsequence，使得在S1, S2都以相同次序出现过，但不要求连续.
用DP四步法分析这个问题:
- 最优子结构
- 最优解的递归结构
c[i, j]是X_i, Y_j的LCS.
如果x_i = y_j，那么直接添加这个字符到LCS. 如果 x_i != yj，那么就变成了两个subproblem: 寻找X{i-1}和Y_j的LCS和寻找Xi和Y{j-1}的LCS.
- 自底向上计算最优值
- 构建最优解
左上的斜线表示x_i = y_j. 斜线的地方表示的就是LCS.
print出来是这样:
Optimal binary search trees
就是有n个keys，每个key有一个概率p; 如果查询未果，还有n+1个dummy keys，每个dummy key也有一个概率q.
有
后面不想看了....
本科时候啃过一部分. 现在的目的是学习跟组合优化有关的部分. 对高级数据结构等内容不感兴趣.
先看第四部分Advanced Design and Analysis Techniques. selected topics也有一些ch值得读.
solutions: https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html
讲道理, CLRS的写作非常棒，简洁易懂. 感觉写paper可以学习一个.