Dynamic Programming, 动态规划

这组问题的分类上基本延续了九章高级算法班的大纲，加了些听课时候的笔记，和自己之后查资料的思考。

动态规划问题的种类更杂，一般来讲也更 tricky 一些。因为这类问题建立在对问题的状态空间和子问题结构有清晰的认识，并且能正确定义和缓存子问题结果上。即使最后的代码看起来可能只是几个循环，但是从复杂程度上大多数要高于暴力搜索和二叉树。

见到题基本的判断，用 DP 做的题大多返回 boolean / int ，求 Max /Min ，而且不能打乱原输入顺序。

动态规划有两个重要定义，一个叫 "optimal substructure"，另一个叫 "overlap subproblem".

各种排序 / Tree 类问题中，都会用到 divide & conquer 的思想，去把问题分成若干个 "disjoint" subproblems，然后递归解决。

"Disjoint" subproblem 在 Tree 类问题上体现的最为明显，左子树是左子树的问题，右子树是右子树的问题。因此 Tree 类问题上，更多的是解决“disjoint subproblem 的整合” 还有 “非连续 subproblem 的处理”。

而动态规划的中心思想是，面对 search tree 里都是 "overlap subproblem"，如何根据问题结构制定缓存策略，避免重叠问题重复计算。

根据CLRS，动态规划分为两种：

• top-down with memoization (递归记忆化搜索)

  • 等价于带缓存的，搜索树上的 DFS

  • 比较贴近于新问题正常的思考习惯

• bottom-up (自底向上循环迭代)

  • 以 "reverse topological order" 处理

  • 每个子问题下面依赖的所有子问题都算完了才开始计算当前

  • 一般依赖于子问题之间天然的 "size" 联系

两种解法 big-O 时间复杂度一致，bottom-up 的 constant factor 小一些。

Rod-Cutting 的"subproblem graph"（子问题图），可以看到如果以 "subtree" 为单位定义 "subproblem" 的话，这个子问题图的结构有非常多的 "identical subtree" ，也即多个 "overlap subproblem". 这样结构的子问题图有 2^N 的节点和 2^(N-1) 个叶节点，不做任何记忆化搜索的话必然是指数级时间复杂度。

因此，动态规划的时间复杂度分析和子问题图 G = (V,E) 的结构息息相关。V = Vertex，代表每一个子问题； E = Edge，代表子问题之间结构。一般来讲，解决一个子问题的时间复杂度和其对应 V 的 out-degree 成正比；子问题的数量等于 V 的数量，既然每个子问题只被计算一次，在整个子问题图上做动态规划的复杂度，和 O(E + V) 成正比。

动态规划的另一个要素是 "optimal substructure":

• A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.

• optimal substructure 指，一个问题的最优解，可以由其子问题的最优解构造出来。

What is optimal/non-optimal substructure? A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem What is local and global optimum? Local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. Global optimum - is the optimal solution among all possible solutions, not just those in a particular neighborhood of values. How to prove that Greedy algorithm yields global optimum? Usually, global optimum can be proven by induction. Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step. Otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is used. To prove that an optimization problem can be solved using a greedy algorithm, we need to prove that the problem has the following:

• Optimal substructure property: an optimal global solution contains the optimal solutions of all its subproblems.

• Greedy choice property: a global optimal solution can be obtained by greedily selecting a locally optimal choise.

• Matroids can be used as well in some case used to mechanically prove that a particular problem can be solved with a greedy approach.

You will find yourself following a common pattern in discovering optimal substructure:

1. You show that a solution to the problem consists of making a choice, such as choosing an initial cut in a rod or choosing an index at which to split the matrix chain. Making this choice leaves one or more subproblems to be solved.

2. You suppose that for a given problem, you are given the choice that leads to an optimal solution. You do not concern yourself yet with how to determine this choice. You just assume that it has been given to you.

3. Given this choice, you determine which subproblems ensue and how to best characterize the resulting space of subproblems.

4. You show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal by using a “cut-and-paste” technique. You do so by supposing that each of the subproblem solutions is not optimal and then deriving a contradiction. In particular, by “cutting out” the nonoptimal solution to each subproblem and “pasting in” the optimal one, you show that you can get a better solution to the original problem, thus contradicting your supposition that you already had an optimal solution. If an optimal solution gives rise to more than one subproblem, they are typically so similar that you can modify the cut-and-paste argument for one to apply to the others with little effort.