# Dynamic Programming

CREATED: 200701080618 ** Types of DP *** 1D/1D: $E[j] = min_{0 \le i \lt j}(D[i] + w(i,j))$ for $1 \le j \le n$

• least weight subsequence
• optimal paragraph formation
• finding a minimum height B-tree
• sequence alignment with gaps (2n copies of Problem 1)
• number of problems in computational geometry *** 2D/0D: E[i,j] = min(D[i-1,j] + x_i, D[i,j - 1] + y_j, D[i - 1, j - 1] + z_(i,j)) for 1 le i,j le n
• string edit distance
• longest common subsequence
• sequence alignment
• sequence alignment with linear gap costs *** 2D/1D: C[i,j] = w(i,j) + min_(i lt k le j)(C[i, k - 1] + C[k, j]) for 1 le i lt j le n
• optimal binary search trees
• maximum perimeter inscribed polygon
• contruction of optimal t-ary tree *** 2D/2D: E[i,j] = min_(0 le i' lt i, 0 le j' lt j)(D[i',j'] + w(i' + j', i + j) for 1 le i,j le n
• secondary structure of RNA without loops

** Convexity and concavity

• Cost function w is convex/concave if it satisfied the convex/concave Monge condition: ** Convex: w(a,c) + w(b,d) le w(b,c) + w(a,d), AA a < b and c < d ** Concave: w(a,c) + w(b,d) ge w(b,c) + w(a,d), AA a < b and c < d
• Matrix A is convex/concave totally monotone if for all a < b and c < d, ** Convex: A[a,c] ge A[b,c] => A[a,d] ge A[b,d] ** Concave: A[a,c] le A[b,c] => A[a,d] le A[b,d]
• Let r_j be the row index such that A[r_j,j] is the minimum value in column j
• Convex total monotonicity => r_1 le r_2 le cdots le r_m
• Concave total monotonicity => r_1 ge r_2 ge cdots ge r_m
• Convex (concave) monge condition => convex (concave) total monotonicity, but the converse is not true
• Algorithms only require total monotonicity to work
• Dead ** A[i,j] is dead if i != r_j ** A[i:i’, j:j’] is dead if all elements inside are dead

** 1D/1D problem

• if D[i] = E[i] and w(i,i) = 0 (w satisfies the triangle inequality or inverse triangle inequality) then: ** Convex: E[j] = D + sum_(0 le k lt j) w(k, k + 1) ** Concave: E[j] = D + w(0,j)

** Steps

# Define the “correct” problem

** use all parameters ** the solution as a special case ** make use of history

# Extract the DP

** Reference

• Dynamic Programming with Convexity, Concavity and Sparsity