Dynamic Programming

Table of Contents

Solve problem by breaking down into simpler sub-problems.

1 One dimension

Given n, find the number of different ways to write n as the sum of 1,3,4

1.1 Define sub-problems

Dn is the number of ways to write n as sum of 1,3,4

1.2 Recurrence formula

Dn = Dn-1 + Dn-3 + Dn-4

2 Two Dimensions

Given two string x and y, find the length of longest common sub-sequence.

2.1 Define sub-problems

Dij is the length for xi..i and y1..j

2.2 Recurrence formula

Dij =

  • if xi = yi: Di-1,j-1 + 1
  • otherwise: max{Di-1,j, Di,j-1}

3 Interval DP

Given a string x=x1..n, find the minimum number of characters that need to be inserted to make it a palindrome.

3.1 Define sub-problem

Di,j be the minimum number of characters.

3.2 Recurrence formula

say y1..k is the palindrome for xi..j, we have either y1 = xi or yk = xj

Dij =

  • if xi ≠ xj: 1 + min{Di+1,j, Di,j-1}
  • if xi = xj: Di+1,j-1

4 Tree DP

Given a tree, color nodes black as many as possible without coloring two adjacent nodes.

4.1 Define

  • B(r) as the maximum nodes if the (root) node r is colored black.
  • W(r) as the maximum nodes if the (root) node r is colored white.

4.2 Recurrence

  • B(v) = 1 + ∑children W(c)
  • W(v) = 1 + ∑children max{B(c), W(c)}