Dynamic Programming

What is Dynamic Programming

动态规划（Dynamic Programming，DP）是一种优化策略，可以解决一系列具有相同属性的复杂问题集。这种问题是可以被暴力递归或者迭代解决的，动态规划是用来优化解决方案的，这种简单的优化将时间复杂度从指数级降（O(c^n) - O(2^n)）低到多项式级（O(n^c) - O(n^2)）。有时甚至简化重复运算可以得到O(n)的时间复杂度。这些问题的类型通常是：

  • 计数问题 counting
  • 求最值问题
  • 最优策略的问题
  • 判断是否存在的问题， 可行性问题

这些问题往往具有相同的属性：

  • 最优子结构 Optimal substructure
  • 重叠子问题 Overlapping subproblems

重叠子问题

与分而治之(Divide and Conquer)一样，动态规划结合了子问题的解决方案。动态规划主要用于需要反复解决相同子问题的情况。在动态规划中，子问题的计算结果存储在一个表中，因此不必重新计算。如果知道了第n个问题的答案，那么第n+1个问题的答案不用从头开始计算，而是通过第n个问题的答案可以很快得到。例如，二分查找没有共同的子问题。如果我们以斐波那契数列的递归程序为例，就会有许多子问题被一次又一次地解决。

最优子结构

在动态规划中，最优子结构属性指的是可以从子问题的答案构建复杂问题的答案的方式。此属性用于规划动态规划计算，通过将问题分解为更小的子问题，然后合并这些子问题的答案以获得整个问题的答案。

How to Find DP problems

combinatoric problems (how mang)

optimization problems (what is the minimum / maximum)

Solution

  1. Define the objective function

  2. Identify base cases

  3. Write down a recurrence relation for the optimized objective function

  4. What’s the order of execution?

  5. Where to look for the answer?

动态规划和 DFS 区别

  • 二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 DFS，就可以解决

  • 像 triangle 这种是有重复走的情况，子问题是有交集，所以可以用动态规划来解决

递归和动规关系

递归是一种程序的实现方式：函数的自我调用

1
2
3
4
5
Function(x) {
    ...
    Funciton(x-1);
    ...
}

动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)

使用场景

满足两个条件

  • 满足以下条件之一

    • 求最大/最小值（Maximum/Minimum ）

  • 求是否可行（Yes/No ）

  • 求可行个数（Count(*) ）

  • 满足不能排序或者交换（Can not sort / swap ）

如题：longest-consecutive-sequence 位置可以交换，所以不用动态规划

四点要素

  1. 状态 State

    • 灵感，创造力，存储小规模问题的结果

  2. 方程 Function

    • 状态之间的联系，怎么通过小的状态，来算大的状态

  3. 初始化 Intialization

    • 最极限的小状态是什么, 起点

  4. 答案 Answer

    • 最大的那个状态是什么，终点

常见四种题目类型

  1. Matrix DP (10%)

  2. Sequence (40%)

  3. Two Sequences DP (40%)

  4. Backpack (10%)

Top-Down vs. Bottom-Up

top-down 和 bottom-up都是信息处理的策略，用于各个领域，比如管理，心理学，制造业和计算机。在心理学中，感知是组织和解释感官信息的工程，有两种方式top-down 和 bottom-up。bottom-up方式是处理实时的信息。top-down方式是在处理更详细的信息之前先从一个更宏观的角度开始，从大局到细节。

回到计算机科学当中，top-down方式是基于计划和对系统的全面理解，通过将整个问题分成子模块实施策略。然后所有的子模块稍后实现。这种方式更适合于从头开始设计软件解决方案并且非常具体的细节未知的情况下。

bottom-up方式正相反，从小组件开始实现，将实现好的小组件组装到所需的系统当中。这种方式适用于需要从一些现有的组件创建系统的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// top-down
main() {
    init()
    worker()
}

worker() {
    initWorker()
    runLogic()
}

// bottom-up
import worker
import runner


main() {
    myWrk = work.new()
    myWrk.init()

    runner.run(worker)
}

举例 Fibonacci sequence

f(n) = f(n-1) + f(n - 2)

top-down : f(n) -> f(3) -> f(2) -> f(1)

bottom-up : f(1) -> f(2) -> f(3) -> f(n)

有人说bottom-up是真的Dynamic Programming， top-down只是递归+记忆

bottom-up可以解决所有问题， top-down只是解决我们需要解决的问题

bottom-up也叫tabulation，因为我们使用一个arr来解决问题，针对特定问题，我们会创建一个n的数组来储存每个f的值，bottom-up这样的工作方式会使用迭代，不容易产生堆栈溢出的错误。而top-down方式解决问题的时候，如果整个递归树太深，容易产生堆栈溢出的错误。

关于bottom-up有两种方式来计算子问题，

  • 正向动态规划：知道多个子问题的结果 -> 一个未知的子问题

  • 反向动态规划：知道一个子问题的结果 -> 多个未知的子问题