Dynamic Programming

Weighted interval scheduling (Binary Choice of Opti Sub)

  • Jobjjstarts at sjs_j, finishes at fjf_j, and has weight wj>0w_j>0.

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

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

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

To efficiently computer p(j)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

OPT(j)={0if j=0max{OPT(j−1),wj+OPT(p(j))if j>0\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=0j=0means 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)=OPT( i) = max sum of any subarray of xx whose rightmost index is ii.

Bellman equation

OPT(i)={xiif i=1max{xi,xi+OPT(i−1)if i>1\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=1i=1means 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 nn items: item ii provides value vi>0v_i > 0 and weighs wi>0w_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)=OPT(i, w) = optimal value of knapsack problem with items 1,…,i,1, …, i, subject to weight limit ww.

Bellman equation

OPT(i,w)={0if i=0OPT(i−1,w)if wi>wmax{OPT(i−1,w),vi+OPT(i−1,w−wi)otherwise\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=0i=0means 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 d1,d2,…,dn{ d_1 , d_2 , …, d_n } and a target value VV, find the fewest coins needed to make change for VV (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)=OPT(v) =min number of coins to make change forvv. (The current subproblem can be set by choosing any coin denomination. (Multi-way choice))

Bellman equation

OPT(v)={∞if v<00if v=0min⁡1≤i≤n{1+OPT(v−di)}if v > 0\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<0v<0means 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 = b1,b2,…,bnb_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 (bi,bj)∈S(b_i , b_j ) ∈ S, theni<j–4 i < j – 4.

  3. [Non-crossing] If (bi,bj)(b_i , b_j ) and (bk,bℓ)(b_k , b_ℓ ) are two pairs in SS, then we cannot have i<k<j<ℓi < k < j < ℓ.

Goal. Given an RNA moleculeB=b1b2…bnB = b_1b_2 …b_n, find a secondary structure SS 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)=OPT(i, j) =maximum number of base pairs in a secondary structure of the substring B=b1b2…bnB = b_1b_2 …b_n

Bellman equation

OPT(i,j)={0if i≥j−4max{OPT1(i,j)+OPT(i,j−1)}otherwiseOPT1(i,j)=1+max⁡i≤t≤j−4{OPT(i,t−1)+OPT(t+1,j−1)}\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 ii 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α_{pq}.

  • Cost = sum of gap and mismatch penalties.

Sequence alignment. Given two strings x1x2...xmx_1x_2 ... x_m and y1y2...yny_1y_2 ... y_n , find a min-cost alignment.

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

cost(M)=∑(xi,yj)∈Mαxiyj⏟mismatch+∑xi∈unmatchedα+∑yj∈unmatchedδ⏟gapcost(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)=OPT(i, j) =min cost of aligning prefix strings x1x2...xix_1x_2 ... x_i and y1y2...yjy_1y_2...y_j.

Bellman equation

OPT(i,j)={jδif j=0iδif i=0min{αxiyj+OPT(i−1,j−1)δ+OPT(i−1,j)δ+OPT(i,j−1)otherwise\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*}

  • δ\deltameans gap penalty

  • α\alphameans match penalty. Match zero, mismatch 1.

PreviousBisectNextDivide and Conquer

Last updated

Was this helpful?