Unit 4 NineChap : Dynamic programming - part I

• 今天开始讲Dynamic Programming.
  • 先讲的前2个常见的DP类型题: Matrix DP和Sequence DP.
  • 下一节课再讲后2个DP类型题: 2 Sequencee DP和Backpack.

DP的实现方式:

1. top-down的recursion: memorization search
2. bottom-up的iteration或者recursion.

如何想到使用DP

• 虽然和recursion都是使用了子问题解决大问题. 不过动归是一种算法思想, 而递归则如同Algs4书本所说: 是一种organize代码的方式.
• 我感觉段老师这里所说的动归是指严格的动归, 他将memorization search作为广义的动归, 到底还是search.
• 如何想到使用动归
  • 满足其中一个条件:
    1. 求极值
    2. 判断是否存在
    3. Count(*)
  • can not sort/swap. 参考LCS(subsequence vs substring)

动归4要素

1. 状态 : 关键的关键. 这个靠经验(参见: 100个动规方程) 相当于几何题目的辅助线. 往往不是一次成功, 要反复的实验. 经典的例子是: LIS.
2. 递推式 : 表述state之间的联系: 如何使用小state来算大state. 这里的大小是段老师定义的. 例如unique path, 小state就是距离起点近的, 大state就是举例起点近, 或者说举例终点近的.
3. 初始条件 : 最极限的小状态. 例如2D DP表就是初始化第一行/第一列.
4. 答案 : 最大的状态.

面试最常见的4种类型

1. Matrix DP(10%)
2. Sequence (40%)
3. 2 Sequence (40%) —- 全都可以用rolling DP!
4. Backpack (10%) —- 可以参考背包九讲2.0