You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

算法 | 动态规划 - Dynamic Programming

. 4 min read

Dynamic Programming

Dynamic programming: Break up a problem into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems.

Weighted Interval Scheduling

Weighted interval scheduling problem.

  • Job j starts at $s_j$, finishes at $f_j$, and has weight or value $v_j$.
  • Two jobs compatible if they don't overlap.
  • Goal: find maximum weight subset of mutually compatible jobs.

Greedy algorithm works when v = 1

Notation. Label jobs by finishing time: $f_1 < f_2 < \dots < f_n$ .

Def. p(j) = largest index i < j such that job i is compatible with j.

能够在 j 之前做的,DDL 最晚的任务

Notation. OPT(j) = value of optimal solution to the problem consisting of job requests 1, 2, ..., j

Case 1: OPT selects job j.

  • collect profit $v_j$
  • can't use incompatible jobs ${ p(j) + 1, p(j) + 2, ..., j - 1 }$
  • must include optimal solution to problem consisting of remaining compatible jobs $1, 2, ..., p(j)$

Case 2: OPT does not select job j.

  • must include optimal solution to problem consisting of remaining compatible jobs $1, 2, ..., j-1$


OPT( j)=\left{
\text{0,}&\quad\text{if j = 0,}\
max{v_j + OPT(p( j)), OPT( j -1)} &\quad\text{otherwise.}

Bottom-up DP

Running Time: $O(n)$

Segmented Least Squares



  • OPT(j) = minimum cost for points $p_i, p_{i+1} , \dots , p_j$
  • e(i, j) = minimum sum of squares for points $p_i, p_{i+1} , \dots , p_j$

To compute OPT(j):

  • Last segment uses points $p_i, p_{i+1} , \dots , p_j$ for some i.
  • Cost = e(i, j) + c + OPT(i-1)

OPT( j)=\left{
\text{0,}&\quad\text{if j = 0,}\
min_{1 \leq i \leq j}{e(i, j) + c + OPT(i-1)} &\quad\text{otherwise.}

Running time. $O(n^3)$.

can be improved to $O(n^2)$ by pre-computing various statistics

Bottleneck = computing e(i, j) for O(n2) pairs, O(n) per pair using previous formula

Knapsack Problem

Knapsack problem.

  • Given n objects and a "knapsack."
  • Item i weighs wi > 0 kilograms and has value vi > 0.
  • Knapsack has capacity of W kilograms.
  • Goal: fill knapsack so as to maximize total value.

Def.  OPT(i, w) = max profit subset of items 1, …, i with weight limit w.

  • Case 1: OPT does not select item i.
    – OPT selects best of { 1, 2, …, i-1 } using weight limit w
  • Case 2: OPT selects item i.
    – new weight limit = w – $w_i$
    – OPT selects best of { 1, 2, …, i–1 } using this new weight limit


OPT(i, w)=\left{
\text{0,}&\quad\text{if j = 0,}\
\text{OPT(i-1, w)}&\quad if w_i > w,\
max{OPT(i-1, w), v_i + OPT(i-1, w- w_i)} &\quad\text{otherwise.}

Running time. $O(n W)$.

  • Not polynomial in input size!
  • "Pseudo-polynomial."
  • Decision version of Knapsack is NP-complete. [Chapter 8]

RNA Secondary Structure

Sequence Alignment

Sequence Alignment in Linear Space


Shortest Paths

Dijkstra 要求每条边的权重均为正整数,若出现负数,则会陷入负数环中

Def. OPT(i, v) = length of shortest v-t path P using at most i edges

  • Case 1: P uses at most i-1 edges.
  • OPT(i, v) = OPT(i-1, v)
  • Case 2: P uses exactly i edges.
    – if (v, w) is first edge, then OPT uses (v, w), and then selects best
    w-t path using at most i-1 edges

OPT(i, v)=\left{
\text{0,}&\quad\text{if i = 0,}\
min{OPT(i-1, v), min_{v, w ∈ E}{OPT(i-1, w) + c_{vm}}} &\quad\text{otherwise.}


Remark. By previous observation, if no negative cycles, then OPT(n-1, v) = length of shortest v-t path.


Analysis. $\Theta(mn)$ time, $\Theta(n^2)$ space.

Finding the shortest paths. Maintain a "successor" for each table entry.

Practical Improvements

  • Maintain only one array M[v] = shortest v-t path that we have found so far (i : 1, 2, … n-1).
  • No need to check edges of the form (v, w) unless M[w] changed in previous iteration.

Theorem. Throughout the algorithm, M[v] is length of some v-t path,
and after i rounds of updates, the value M[v] is no larger than the length
of shortest v-t path using $\leq$ i edges.
Overall impact.

  • Memory: $O(m + n)$.
  • Running time: $O(mn)$ worst case, but substantially faster in practice.