Dynamic Programming (DP)
- Powerful algorithmic design technique
- Large class of seemingly exponential problems have a polynomial solution (“only”) via DP
- Particularly for optimization problems (min / max) (e.g., shortest paths)
- DP $\approx$ “controlled brute force”
- DP $\approx$ recursion + re-use
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-comupute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
Fibonacci Numbers
$$F1 = F2 = 1; \qquad F_n = F_{n−1} + F_{n−2}$$
Goal: compute $F_n$
Naive Algorithm1
2
3fib(n):
if n <= 2: return f=1
else: return f = fib(n-1) + fib(n-2)
⇒ $T(n) = T(n − 1) + T(n − 2) + O(1) ≥ Fn ≈ ϕ^n$
$≥ 2T(n − 2) + O(1) ≥ 2n/2$
EXPONENTIAL — BAD!
(As some items will be calculated twice, which consumes times)
Memoized DP Algorithm1
2
3
4
5
6
7memo = { }
fib(n):
if n in memo: return memo[n]
else: if n ≤ 2 : f = 1
else: f = fib(n − 1) + fib(n − 2)
memo[n] = f
return f
Remember:
• ⇒ fib(k) only recurses first time called, ∀k
• ⇒ only n nonmemoized calls: k = n, n − 1, . . . , 1
• memoized calls free ($Θ(1)$ time)
• ⇒ $Θ(1)$ time per call (ignoring recursion)
POLYNOMIAL — GOOD!
DP ≈ recursion + memoization
- memoize (remember) & re-use solutions to subproblems that help solve problem
- in Fibonacci, subproblems are F1, F2, . . . , Fn
- ⇒ time = # of subproblems x time/subproblem
- Fibonacci: # of subproblems is n, and time/subproblem is Θ(1) = Θ(n) (ignore recursion!).
Bottom-up DP Algorithm1
2
3
4
5
6fib = {}
for k in [1, 2, . . . , n]:
if k ≤ 2: f = 1
else: f = fib[k − 1] + fib[k − 2]
fib[k] = f
return fib[n]
- exactly the same computation as memoized DP (recursion “unrolled”)
- in general: topological sort of subproblem dependency DAG
- practically faster: no recursion
- analysis more obvious
- can save space: just remember last 2 fibs ⇒ Θ(1)
Shortest Paths
- Recursive formulation:
$$δ(s, v) = min{δ(s, u) + w(u, v) | (u, v) ∈ E}$$ - Memoized DP algorithm: takes infinite time if cycles!
- in some sense necessary to handle negative cycles
- works for directed acyclic graphs in $O(V + E)$
- effectively DFS/topological sort + Bellman-Ford round rolled into a single recursion
Subproblem dependency should be acyclic
- effectively DFS/topological sort + Bellman-Ford round rolled into a single recursion
- more subproblems remove cyclic dependence:
$$δ_k(s, v) = shortest \quad s → v \quad path \quad using ≤ k \quad edges$$ - recurrence:
$δk(s, v) = min{δ{k−1}(s, u) + w(u, v)|(u, v) ∈ E}$
$δ_0(s, v) = ∞$ for s $\ne$ v (base case)
$δ_k(s, s) = 0$ for any k (base case, if no negative cycles)$ - Goal: $δ(s, v) = δ_{|V|−1}(s, v)$ (if no negative cycles)
- memorize
- time: # of subproblems($|V|·|V|$) x time/subproblem($O(v) = 0(V^3)$)
- actually $Θ(indegree(v))$ for $δ_k(s, v)$
- ⇒ time = $Θ(V\sum_{v∈V} indegree(V)) = Θ(VE)$
Guessing
How to design recurrence:
- want shortest s → v path
- what is the last edge in path? dunno
- guess it is (u, v)
- then path is shortest s → u path + edge(u, v)
- the cost is $δ{k−1}(s, u) + w(u, v)$, and $δ{k−1}(s, u)$ is another subproblem
- to find best guess, try all (|V| choices) and use best
- key: small (polynomial) # possible guesses per subproblem — typically this dominates time/subproblem
DP ≈ recursion + memoization + guessing
Summary
- DP $\approx$ “careful brute force”
- DP $\approx$ guessing + recursion + memoization
- DP ≈ dividing into reasonable # of subproblems whose solutions relate - acyclicly - usually via guessing parts of solution.
- time = # subproblems × time/subproblem
- essentially an amortization
- count each subproblem only once; after first time, costs O(1) via memoization
- DP ≈ shortest paths in some DAG
5 Easy Steps to Dynamic Programming
- define subproblems count # subproblems
- guess (part of solution) count # choices
- relate subproblem solutions compute time/subproblem
- recurse + memoize time = time/subproblem x # subproblems
- OR build DP table bottom-up
- check subproblems acyclic/topological order
- solve original problem: = a subproblem
- OR by combining subproblem solutions ⇒ extra time
Examples
Text Justification
Content:
Split text into good lines
- obvious(MS Word) algorithm: put as many words that fit on first line, repeat
- but this can make very bad lines
Redefine the problem: - Define badness(i,j) for line of words: [i,j]
- e.g. if $\inf$ total length > page width, else (page width - total length)^3
- goal: split words into lines to min $\sum$ badness
- subproblem = min. badness for suffix words[i :]
⇒ number of subproblems = Θ(n) where n = number of words - guessing = where to end first line, say i:j
⇒ number of choices = $n − i = O(n)$ - recurrence:
• DP[i] = min(badness (i,j) + DP[j] for j in range (i+1,n+1))
• DP[n] = 0
⇒ time per subproblem = Θ(n) - order: for i=n,n-1,…,1,0
total time = $Θ(n^2)$ - solution = DP[0]
Reference:
https://www.geeksforgeeks.org/dynamic-programming/