Dynamic Programming

Weighted interval scheduling (Binary Choice of Opti Sub)

• Job$j$starts at $s_j$, finishes at $f_j$, and has weight $w_j>0$.

• Two jobs are compatible if they don’t overlap.

• Goal: find a max-weight subset of mutually compatible jobs.

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

To efficiently computer $p(j)$we can sort jobs in ascending order of finish time.

• Constraints on the interval time (subproblem)

• Seek max weights (open values)

Optimum Subproblem

Max weight with an increasing ordering subset of mutually compatible intervals.

Bellman equation

$$\begin{equation*} OPT(j)= \begin{cases} 0 &\text{if $j=0$}\\ max\{OPT(j-1), w_j + OPT(p(j)) &\text{if $j > 0$} \end{cases} \end{equation*}$$

$j=0$means empty set and no intervals scheduled

Subproblem is a binary choice problem.

Maximum Continuous Subarray Sum-KADANE ’ S ALGORITHM (Binary Choice of Opti Sub)

• Constraints on the continuous subarray (subproblem)

• Seek max weights (open values)

Optimum Subproblem

Max sum with an increasing ending index. (or increasing ordering subset)

$OPT( i) =$ max sum of any subarray of $x$ whose rightmost index is $i$.

Bellman equation

$$\begin{equation*} OPT(i)= \begin{cases} x_i &\text{if $i=1$}\\ max\{x_i, x_i + OPT(i-1) &\text{if $i > 1$} \end{cases} \end{equation*}$$

$i=1$means first element or subset with length of 1

Subproblem is a binary choice problem.

Knapsack problem (Two variable Opti Subp)

Goal. Pack knapsack so as to maximize the total value of items taken.

• There are $n$ items: item $i$ provides value $v_i > 0$ and weighs $w_i > 0$.
• Value of a subset of items = sum of values of individual items.

• The Knapsack has a weight limit of W.

• Constraints on the weights and at most 1 items for each item (subproblem)

• Seek max values (open values)

Optimum Subproblem

Max value with an increasing ending index with a change of weight limit. (or increasing ordering subset)

$OPT(i, w) =$ optimal value of knapsack problem with items $1, …, i,$ subject to weight limit $w$.

Bellman equation

$$\begin{equation*} OPT(i, w)= \begin{cases} 0 & \text{if $i=0$}\\ OPT(i-1,w) &\text{if $w_i>w$}\\ max\{OPT(i-1, w), v_i + OPT(i-1, w-w_i) &\text{otherwise} \end{cases} \end{equation*}$$

$i=0$means empty set and no item gets loaded

The Subproblem is a two-variable problem. (Constraints is weight limit updating, compared to a compatible interval scheduling)

Coin Changing (Multiway-choice Opti Subp)

Goal. Given n coin denominations ${ d_1 , d_2 , …, d_n }$ and a target value $V$, find the fewest coins needed to make change for $V$ (or report impossible).

• Constraints on the change values (subproblem, increasing changes of values, subproblem is created by choosing any coins currently)

• Seek max number of coins (open questions, because for each coin we do not know we need how many)

Optimum Subproblem

The minimum number of coins with an increasing value of changes.

$OPT(v) =$min number of coins to make change for$v$. (The current subproblem can be set by choosing any coin denomination. (Multi-way choice))

Bellman equation

$$\begin{equation*} OPT(v)= \begin{cases} \infty & \text{if $v<0$}\\ 0 &\text{if $v=0$}\\ \displaystyle \min_{1\le i\le n}\{1 + OPT(v-d_i)\} &\text{if v > 0} \end{cases} \end{equation*}$$

$v<0$means the value there are no possible changes such that the value is $$\infty$$ because we are seeking a minimum number

The Subproblem is a multiway problem, a single-variable problem. (Constraints is weight limit updating, compared to a compatible interval scheduling)

• Coin changing is like the opposite problem of Knapsack problem which one is with fixed values to seek a minimum number of items, the other is with at most one present for each item to seek a maximum possible values.

RNA(String) secondary structure (Substring) (Intervals Opti Subp)

RNA. String B = $b_1, b_2, …,b_n$ over alphabet { A, C, G, U }.

Secondary structure. RNA is single-stranded so it tends to loop back and form base pairs with itself with the following rules:

1. [Watson–Crick] Pairs with Watson–Crick complement: A–U, U–A, C–G, or G–C.

2. [No sharp turns] The ends of each pair are separated by at least 4 intervening bases. If $(b_i , b_j ) ∈ S$, then$i < j – 4$.
3. [Non-crossing] If $(b_i , b_j )$ and $(b_k , b_ℓ )$ are two pairs in $S$, then we cannot have $i < k < j < ℓ$.

Goal. Given an RNA molecule$B = b_1b_2 …b_n$, find a secondary structure $S$ that maximizes the number of base pairs.

• Constraints on the substrings

• (subproblem, increasing ending index of the substring, subproblem is created by choosing any letter that comes before the current letter to form two new substrings.)

• These two substrings for the subproblems form an interval optimal subproblems.

• Seek max number of Watson-Crick pairs

Optimum Subproblem

The maximum number of WC pairs with an increasing ending index of the substring. Each subproblem is solved by all substrings within.

$OPT(i, j) =$maximum number of base pairs in a secondary structure of the substring $B = b_1b_2 …b_n$

Bellman equation

$$\begin{equation*} OPT(i, j)= \begin{cases} 0 & \text{if $i\ge j-4$}\\ \displaystyle max\{OPT_1(i, j) + OPT(i, j-1)\} & \text{otherwise} \end{cases} \end{equation*}\\ OPT_1(i, j) = 1 + \displaystyle \max_{i\le t\le j-4}{\{OPT(i, t-1) + OPT(t+1, j-1)\}}$$

• 1 means pair (t, j)

• The subproblem is a two-interval problem

• If it is an interval subproblem then the starting index $i$ should be iterated. (Ordering increasing subsets with an iterating starting index)

RNA-SECONDARY-STRUCTURE (n, b_1 , …, b_n )

FOR k = 5 TO n – 1
    FOR i = 1 TO n – k
        j ← i + k.
        Compute M[i, j] using formula.
RETURN M[1, n].

Sequence Alignment (Substring) (Two-Variable Opti Subp)

Edit distance. [Levenshtein 1966, Needleman–Wunsch 1970]

• Gap penalty $δ$; mismatch penalty $α_{pq}$.
• Cost = sum of gap and mismatch penalties.

Sequence alignment. Given two strings $x_1x_2 ... x_m$ and $y_1y_2 ... y_n$ , find a min-cost alignment.

An alignment M is a set of ordered pairs $x_i – y_j$ such that each character appears in at most one pair and no crossings.

$cost(M) = \displaystyle \underbrace{\sum_{(x_i, y_j) \in M}α_{x_iy_j}}_{\text{mismatch}} + \underbrace{\sum_{x_i \in unmatched}\alpha + \sum_{y_j \in unmatched}\delta }_{\text{gap}}$

• Constraints on the two substrings

• (subproblem, increasing ending index of the two strings)

Optimum Subproblem

The minimum cost of alignment with an increasing ending index of the two substrings.

$OPT(i, j) =$min cost of aligning prefix strings $x_1x_2 ... x_i$ and $y_1y_2...y_j$.

Bellman equation

$$\begin{equation*} OPT(i, j)= \begin{cases} j\delta & \text{if $j=0$}\\ i\delta & \text{if $i=0$}\\ min\begin{cases} \alpha_{x_iy_j} + OPT(i-1, j-1) \\ \delta + OPT(i-1, j)\\ \delta + OPT(i, j-1)\\ \end{cases} & \text{otherwise} \end{cases} \end{equation*}$$

• $\delta$means gap penalty
• $\alpha$means match penalty. Match zero, mismatch 1.