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$

由此可知，其状态转移方程为：

$$\begin{equation}OPT( j)=\left{\begin{array}{lr}\text{0,}&\quad\text{if j = 0,}\max{v_j + OPT(p( j)), OPT( j -1)} &\quad\text{otherwise.}\end{array}\right.\end{equation}$$

Bottom-up DP

Running Time: $O(n)$

Segmented Least Squares

Intro.

Notation

• 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)

$$\begin{equation}OPT( j)=\left{\begin{array}{lr}\text{0,}&\quad\text{if j = 0,}\min_{1 \leq i \leq j}{e(i, j) + c + OPT(i-1)} &\quad\text{otherwise.}\end{array}\right.\end{equation}$$

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

必须考虑重量的限制

$$\begin{equation}OPT(i, w)=\left{\begin{array}{lr}\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.}\end{array}\right.\end{equation}$$

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 bestw-t path using at most i-1 edges

$$\begin{equation}OPT(i, v)=\left{\begin{array}{lr}\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.}\end{array}\right.\end{equation}$$

该算法在不断地更新起点

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

Implementation:

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 lengthof 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.