算法 tips

incremental approach
增量法

divide-and-conquer.
Divide the problem into a number of subproblems.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original prob-
lem.

Divide and Conquer 是 top-down 的解决方案。它的子问题是独立的，因此不会造成冗余。

动态规划
1. optimal substructure
Recall that a problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
2. Overlapping subproblems
动态规划是 tabular, bottom-up 的。
1. Characterize the structure of an optimal solution. 即分析它的 optimal substructure
2. Recursively define the value of an optimal solution. 即列出一个递归解决的式子，它包含 选择某一个 choice
3. Compute the value of an optimal solution in a bottom-up fashion. 这一步是最重要的。一般要手动画一画，从 recusion tree 的 root 走到树叶，然后想想表格的形式。用表格记录 costs，如果需要最优解，则还需用表格记录 choices
4. Construct an optimal solution from computed information.

Trick:
是否是路径问题？
如果是路径问题，则每一个 step 都是必须经过的，所以 choices 可以是“最后一个 step 选择哪个子路径？”

如果是序列问题，则 choices 可以是“序列中的某一个被选中”，subproblem 为前序列和后序列。

有些问题看起来是集合，但是可以把集合的元素进行排序，变成序列问题。比如“An activity-selection problem”。
为什么要排序？
排序的作用是使得子问题的解在子序列中，而不会超出子序列：保证 Sij 的解在 {ak},k=i+1,..j-1

因此，按照开始时间排序也是可以的。假设不排序，上面的要求不满足。

如果排序没有意义，可以尝试“从最后一个开始”，比如0-1 knapsack 问题。
表格可能为 NxN,也可能为 NxW,W为另一个维度。

解决某一个问题，可以转化为使用其他子问题。比如连续子序列最大和问题，实际上子问题是“最大后缀子序列和”。而连续子序列最大和必定为“最大后缀子序列和”的最大的一个。

二叉树的深度优先遍历
前序，中序和后序遍历都是深度优先遍历的特例。区别只在于 previsit 和 postvisit