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)}