Dynamic Programming:Intermediate
Horace He
CS 5199 November 18, 2019
About me
Senior in CS & Math
I’m on Cornell Tank Cadets, and we advanced to�Worlds this year!
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
What is Dynamic Programming (DP)?
Wikipedia definition: “Method for simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner”
Q: But how do we actually solve DP problems?
A:
Components of a DP Solution
State
What’s the subproblem you’re breaking your solution into?
Recurrence
Given your subproblems, how do you solve your actual problem?
Base Case
When breaking up into subproblems, where do you stop?
Implementation
How do we actually implement this? Recursively? Iteratively? Do we need any optimizations?
Typical Solve Process
Problem: Frogs
There are N stones numbered 1,2,.. N. Each stone has a height hi. There is a frog initially on stone 1. At each step, the frog can jump up to K stones ahead, incurring a cost |hi-hj|, where j is the stone the frog lands on.
Formally, if the frog is currently on stone i, it can jump to one of the following stones: i+1, i+2, …, i+K.
Find the minimum possible total cost for the frog to reach stone N.�N<=1e5, K<=100, hi<=1e4
�
N=5, K=3 H=[10,30,40,50,20] | 30 |
N=3, K=1 H=[10,20,10] | 20 |
N=10, K=4 H=[40,10,20,70,80,10,20,70,80,60] | 40 |
Solution: Frogs
State
Recurrence
Base Case
Complexities�Time = O(NK), Memory = O(N)
Two Main Types of DP Problems
Counting
vs.
Maximization
How many ways…?
What’s the best …?
Note #1:
Find a state that allows us to ignore everything else.
Note #1 (redux):
Find states that we can consolidate.
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
Subset DP
Convex Hull Optimization
Problem: Grid
There is a grid with H rows and W columns. Each cell is either ‘.’ or ‘#’. If the cell is ‘.’, then it’s empty. If it’s ‘#’, then it has a wall.
Haobin will start from the upper left square and reach the bottom right square by repeatedly moving right or down to an adjacent empty square. He CANNOT move up or left.
H,W <= 1000
(H,W)=(3,4) ...# .#.. .... | 3 |
(H,W)=(5,2) .. #. .. .# .. | 0 |
Solution: Grid
Q: When do two states become equivalent from there on out?
A: When they reach the same cell.
Summary: Grid
State
dp[i][j] = # of ways to get to cell i, j
Recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Base Case
dp[0][0] = 1
Complexities�Time = O(HW), Memory = O(HW)
Impl: Top-down vs Bottom-up
Bottom-Up:
Top-down:
https://ideone.com/hGGjH7
https://ideone.com/mJJFgx
Which one to use?
Bottom-Up:
Top-down:
Note #2:
Most competitive programmers use bottom-up when possible due to the performance benefits + common optimizations.
Optimization: Sliding Window
Q: What if we wanted to reduce the memory usage of this solution?
A: Each row only depends on the row before it. If we’re handling row 5, why do we still need to keep row 1?
This brings the memory complexity down to O(N).
Note: Requires bottom-up DP.
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
Subset DP
Convex Hull Optimization
Problem: Palindrome Substring
Given a string S, find the longest palindromic substring.
(If you know string algorithms, pretend you don’t know them).
|S| <= 5000
S = ACCABA | ACCA |
S = ABABABA | ABABABA |
Solution: Palindromic Substring
Let’s use this state:
dp[i] = longest palindromic substring with first i characters
Now, let’s find a recurrence…
Solution: Palindromic Substring
Q: Why couldn’t we proceed further?
A: Our state was too “loose”.
How do we differentiate between these two states when transitioning?
cbaba|b
ccaba|b
Solution: Palindromic Substring
Q: What don’t we care about?
A: Given a palindrome that’s a substring, and we’re trying to extend that palindrome, we only need to look at the 2 characters we’re adding.
a|?????|a
a|ababa|a
a|zzzz|a
Summary: Palindromic Substring
State
dp[l][r] = true if S[l..r] is a palindrome
Recurrence
dp[l][r] = (S[l] == S[r] && dp[l+1][r-1])
Base Case
Complexities�Time = O(|S|2), Memory = O(|S|2)
Note #3:
DP states often benefit from adding more restrictions.
Impl: Interval DP
Q: Can we implement this bottom up?
A: Yes.
Q: Previously, we could just iterate row by row. Can we do that now? Hint: Think about what our initial states are and which states each state depends on.
A: No.
https://ideone.com/DDncmF
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
Problem: Tree Coloring
Given a tree with N nodes, find the number of ways to color each white or black such that no two adjacent nodes are black.
N<=1e5
Answer: 5
WWW, WBB, WBW, WWB, BWW
Solution: Tree Coloring
Q: How do we ignore things in a tree?
A: Trees are convenient for DP, as if you remove any node the tree splits into two smaller trees.
DP like this is sometimes called “subtree DP”
Solution: Tree Coloring
Let’s try out this idea.
dp[cur] = # of colorings using the subtree of cur
Q: Why doesn’t this work? Any ideas for how to fix this? Hint: Remember the previous note (“restrict DP states more”).
A: Modify the previous DP state to have another variable, and modify its representation to be
“# of colorings using the subtree of cur assuming cur is colored C”
Solution: Tree Coloring
State
dp[cur][0] = # of ways to color subtree of node cur assuming that cur is white.
dp[cur][1] = # of ways to color subtrees of node cur assuming that cur is black.
Recurrence
Base Case
dp[leaf][0] = dp[leaf][1] = 1
Complexities�Time = O(|S|2), Memory = O(|S|2)
Impl: Tree DP
Q: Should we implement this top-down or bottom-up?
A: Before a node can be processed, all of its children need to be processed. It’s easier to do top-down.
https://ideone.com/TQIh2S
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
Subset DP
Convex Hull Optimization
Problem: Travelling Salesman Problem
Given a weighted graph with N nodes, find the shortest path that visits every node exactly once (this is exactly the travelling salesman problem).
N<=16
The “obvious” algorithm is O(N!).
Note that NP-Hard merely implies that the problem cannot be solved in polynomial time.
Solution: TSP
Let’s try �dp[S] = min cost to go to all nodes in set S
Q: Does this work?
A: As you might figure out from pattern matching… No.
Q: How do we fix this?
A: Let’s restrict!
Summary: TSP
State
dp[cur][S] = min cost to visit all nodes in set S once and end up at node cur.
Recurrence
Base Case
dp[v][{v}] = 0
Complexities�Time = O(n22n), Memory = O(n*2n)
Impl: Subset DP
Q: How do we use a set as a DP state in our programming language?
A: Most common solution is to use integers as bitsets. Often called Bitset DP
S = {1,2,3,4,5}
A = {1,2, 4}
= 1 1 0 1 0 = 26
Impl: Subset DP - Common Operations
A = {1,4} = 10010
B = {3,4,5} = 00111
A|B = {1,3,4,5} = 10111
A^B = {1,3,5} = 10101
Impl: Subset DP
Q: Top-down or bottom-up?
A: It’s not obvious how to do this bottom up. However, note that a subset always has a lower binary value than its superset.
We can just iterate from 0 to 2N!
A = {1,4} = 10010 = 18
B = {1,3,4,5} = 10111 = 23
Impl: TSP
Outline
DP Introduction
Two-Dimensional DP
Interval DP
Tree DP
Subset DP
Convex Hull Optimization
Problem: Cookie Clicker
Haobin is trying to make as many cookies as possible. Unluckily, he can only bake one cookie a second. To help, he has N (1<=N<=1e5) helpers. Each helper will create vi cookies per second (cps), but requires an upfront cost of ci cookies before he’ll start. Only one person (including himself) can create cookies at a time. What’s the minimum amount of time Haobin needs to earn S (S<=1e9) cookies?
Note that you can buy workers at any point, including non-integer times.
N: 2, S: 9
Helper 1: 2 cps, 3 cost, Helper 2: 5 cps, 4 cost
Answer: We buy Helper 2 as soon as possible, which takes 4 seconds. Then, we reach 9 cookies in 2 more seconds.
Solution?: Cookie Clicker
Note that we’ll only ever want to increase the productivity of our workers. If we’re currently making 6 cps, we’ll never want to pay a cost and switch to 5 cps.
So let’s sort our workers by their cps and use this state.
dp[i] = min time to buy the i-th worker.
But wait, how many helpers could we have again?
Solution: Convex Hull Optimization
Notice the special form of this DP transition. �m=1/V[j], b = dp[i]
It’s a line!
Impl: Convex Hull Optimization