Dynamic Programming

What are the steps for solving a dynamic programming problem?
  1. Define (overlapping) subproblems
  2. Write down the recurrence that relates subproblems
  3. Recognize and solve the base cases
What kinds of dynamic programming problems are there?
  • 1-dimensional DP
  • 2-dimensional DP
  • Interval DP
  • Tree DP
  • Subset DP
What is the recurrence for the LCSLCS (longest common subsequence) problem?

Let XX and YY be the two strings we want to find the length of the LCSLCS of, and XiX_i == <X0X_0 , X1X_1,..., XiX_i> and YjY_j == <Y0Y_0, Y1Y_1,..., YjY_j>.

XiX_i and YjY_j are called prefixes of the strings XX and YY.

Further, let c[i,j]c[i,j] be the length of the optimal LCSLCS of the prefixes XiX_i and YjY_j. Then we can have the relation:

c[i,j]={0 if i=0 or j=0c[i1][j1]+1 if i,j>0 and xi=yimax(c[i,j1],c[i1,j]) if i,j>0 and xiyjc[i, j]=\left\{\begin{array}{ll}0 & \text { if } i=0 \text { or } j=0 \\ c[i-1][j-1]+1 & \text { if } i, j>0 \text { and } x_{i}=y_{i} \\ \max (c[i, j-1], c[i-1, j]) & \text { if } i, j>0 \text { and } x_{i} \neq y_{j}\end{array}\right.

What is the recurrence for the LPS (longest palindromic subsequence) problem?
What is the recurrence for the LRS (longest repeated subsequences) problem?
What is the recurrence for the SCS (shortest common supersequence) problem?
What is the recurrence for the LIS (longest increasing subsequence) problem?
What is the recurrence for the Matrix Chain Multiplication problem?
0-1 Knapsack problem (discrete)
0-1 Knapsack problem (continuous)
Diff Utility
04-dynamic-programming.pdf171.6KB