Dynamic Programming
Jaehyun Park
CS 97SI
Stanford University
June 29, 2015
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
Dynamic Programming 2
What is DP?
◮ Wikipedia definition: “method for solving complex problems
by breaking them down into simpler subproblems”
◮ This definition will make sense once we see some examples
– Actually, we’ll only see problem solving examples today
Dynamic Programming 3
Steps for Solving DP Problems
1. Define subproblems
2. Write down the recurrence that relates subproblems
3. Recognize and solve the base cases
◮ Each step is very important!
Dynamic Programming 4
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
1-dimensional DP 5
1-dimensional DP Example
◮ Problem: given n, find the number of different ways to write
n as the sum of 1, 3, 4
◮ Example: for n = 5, the answer is 6
5 = 1+1+1+1+1
= 1+1+3
= 1+3+1
= 3+1+1
= 1+4
= 4+1
1-dimensional DP 6
1-dimensional DP Example
◮ Define subproblems
– Let Dn be the number of ways to write n as the sum of 1, 3, 4
◮ Find the recurrence
– Consider one possible solution n = x1 + x2 + · · · + xm
– If xm = 1, the rest of the terms must sum to n − 1
– Thus, the number of sums that end with xm = 1 is equal to
Dn−1
– Take other cases into account (xm = 3, xm = 4)
1-dimensional DP 7
1-dimensional DP Example
◮ Recurrence is then
Dn = Dn−1 + Dn−3 + Dn−4
◮ Solve the base cases
– D0 = 1
– Dn = 0 for all negative n
– Alternatively, can set: D0 = D1 = D2 = 1, and D3 = 2
◮ We’re basically done!
1-dimensional DP 8
Implementation
D[0] = D[1] = D[2] = 1; D[3] = 2;
for(i = 4; i <= n; i++)
D[i] = D[i-1] + D[i-3] + D[i-4];
◮ Very short!
◮ Extension: solving this for huge n, say n ≈ 1012
– Recall the matrix form of Fibonacci numbers
1-dimensional DP 9
POJ 2663: Tri Tiling
◮ Given n, find the number of ways to fill a 3 × n board with
dominoes
◮ Here is one possible solution for n = 12
1-dimensional DP 10
POJ 2663: Tri Tiling
◮ Define subproblems
– Define Dn as the number of ways to tile a 3 × n board
◮ Find recurrence
– Uuuhhhhh...
1-dimensional DP 11
Troll Tiling
1-dimensional DP 12
Defining Subproblems
◮ Obviously, the previous definition didn’t work very well
◮ Dn ’s don’t relate in simple terms
◮ What if we introduce more subproblems?
1-dimensional DP 13
Defining Subproblems
1-dimensional DP 14
Finding Recurrences
1-dimensional DP 15
Finding Recurrences
◮ Consider different ways to fill the nth column
– And see what the remaining shape is
◮ Exercise:
– Finding recurrences for An , Bn , Cn
– Just for fun, why is Bn and En always zero?
◮ Extension: solving the problem for n × m grids, where n is
small, say n ≤ 10
– How many subproblems should we consider?
1-dimensional DP 16
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
2-dimensional DP 17
2-dimensional DP Example
◮ Problem: given two strings x and y, find the longest common
subsequence (LCS) and print its length
◮ Example:
– x: ABCBDAB
– y: BDCABC
– “BCAB” is the longest subsequence found in both sequences, so
the answer is 4
2-dimensional DP 18
Solving the LCS Problem
◮ Define subproblems
– Let Dij be the length of the LCS of x1...i and y1...j
◮ Find the recurrence
– If xi = yj , they both contribute to the LCS
◮ Dij = Di−1,j−1 + 1
– Otherwise, either xi or yj does not contribute to the LCS, so
one can be dropped
◮ Dij = max{Di−1,j , Di,j−1 }
– Find and solve the base cases: Di0 = D0j = 0
2-dimensional DP 19
Implementation
for(i = 0; i <= n; i++) D[i][0] = 0;
for(j = 0; j <= m; j++) D[0][j] = 0;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(x[i] == y[j])
D[i][j] = D[i-1][j-1] + 1;
else
D[i][j] = max(D[i-1][j], D[i][j-1]);
}
}
2-dimensional DP 20
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
Interval DP 21
Interval DP Example
◮ Problem: given a string x = x1...n , find the minimum number
of characters that need to be inserted to make it a palindrome
◮ Example:
– x: Ab3bd
– Can get “dAb3bAd” or “Adb3bdA” by inserting 2 characters
(one ‘d’, one ‘A’)
Interval DP 22
Interval DP Example
◮ Define subproblems
– Let Dij be the minimum number of characters that need to be
inserted to make xi...j into a palindrome
◮ Find the recurrence
– Consider a shortest palindrome y1...k containing xi...j
– Either y1 = xi or yk = xj (why?)
– y2...k−1 is then an optimal solution for xi+1...j or xi...j−1 or
xi+1...j−1
◮ Last case possible only if y1 = yk = xi = xj
Interval DP 23
Interval DP Example
◮ Find the recurrence
(
1 + min{Di+1,j , Di,j−1 } xi 6= xj
Dij =
Di+1,j−1 xi = xj
◮ Find and solve the base cases: Dii = Di,i−1 = 0 for all i
◮ The entries of D must be filled in increasing order of j − i
Interval DP 24
Interval DP Example
// fill in base cases here
for(t = 2; t <= n; t++)
for(i = 1, j = t; j <= n; i++, j++)
// fill in D[i][j] here
◮ Note how we use an additional variable t to fill the table in
correct order
◮ And yes, for loops can work with multiple variables
Interval DP 25
An Alternate Solution
◮ Reverse x to get xR
◮ The answer is n − L, where L is the length of the LCS of x
and xR
◮ Exercise: Think about why this works
Interval DP 26
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
Tree DP 27
Tree DP Example
◮ Problem: given a tree, color nodes black as many as possible
without coloring two adjacent nodes
◮ Subproblems:
– First, we arbitrarily decide the root node r
– Bv : the optimal solution for a subtree having v as the root,
where we color v black
– Wv : the optimal solution for a subtree having v as the root,
where we don’t color v
– Answer is max{Br , Wr }
Tree DP 28
Tree DP Example
◮ Find the recurrence
– Crucial observation: once v’s color is determined, subtrees can
be solved independently
– If v is colored, its children must not be colored
X
Bv = 1 + Wu
u∈children(v)
– If v is not colored, its children can have any color
X
Wv = 1 + max{Bu , Wu }
u∈children(v)
◮ Base cases: leaf nodes
Tree DP 29
Outline
Dynamic Programming
1-dimensional DP
2-dimensional DP
Interval DP
Tree DP
Subset DP
Subset DP 30
Subset DP Example
◮ Problem: given a weighted graph with n nodes, find the
shortest path that visits every node exactly once (Traveling
Salesman Problem)
◮ Wait, isn’t this an NP-hard problem?
– Yes, but we can solve it in O(n2 2n ) time
– Note: brute force algorithm takes O(n!) time
Subset DP 31
Subset DP Example
◮ Define subproblems
– DS,v : the length of the optimal path that visits every node in
the set S exactly once and ends at v
– There are approximately n2n subproblems
– Answer is minv∈V DV,v , where V is the given set of nodes
◮ Let’s solve the base cases first
– For each node v, D{v},v = 0
Subset DP 32
Subset DP Example
◮ Find the recurrence
– Consider a path that visits all nodes in S exactly once and
ends at v
– Right before arriving v, the path comes from some u in
S − {v}
– And that subpath has to be the optimal one that covers
S − {v}, ending at u
– We just try all possible candidates for u
DS,v = min DS−{v},u + cost(u, v)
u∈S−{v}
Subset DP 33
Working with Subsets
◮ When working with subsets, it’s good to have a nice
representation of sets
◮ Idea: Use an integer to represent a set
– Concise representation of subsets of small integers {0, 1, . . .}
– If the ith (least significant) digit is 1, i is in the set
– If the ith digit is 0, i is not in the set
– e.g., 19 = 010011(2) in binary represent a set {0, 1, 4}
Subset DP 34
Using Bitmasks
◮ Union of two sets x and y: x | y
◮ Intersection: x & y
◮ Symmetric difference: x ˆ y
◮ Singleton set {i}: 1 << i
◮ Membership test: x & (1 << i) != 0
Subset DP 35
Conclusion
◮ Wikipedia definition: “a method for solving complex problems
by breaking them down into simpler subproblems”
– Does this make sense now?
◮ Remember the three steps!
1. Defining subproblems
2. Finding recurrences
3. Solving the base cases
Subset DP 36