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[0] + sum_(0 le k lt j) w(k, k + 1) ** Concave: E[j] = D[0] + w(0,j)

** Steps

Understand the problem and parameters

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

** Reference