Algorithms and Data Structures for Programming Contests
Dynamic Programming
Discussion
What is it?
- A general method for optimization problems whose solution exhibits
the following properties.
- Recursion:
- the problem can be solved by breaking it up into subproblems,
solving those subproblems recursively, and combining the
sub-solutions back into an overall solution.
- Optimal substructure:
- an optimal solution to the problem can always be constructed from
optimal solutions to subproblems, i.e.,
it is never necessary to solve some subproblems sub-optimally
in order to achieve an overall optimal solution.
- Simple subproblems:
- subproblems can be characterized precisely
using a fixed number of "indices".
- Overlapping subproblems:
- subproblems recur multiple times as part of
optimal solutions of the top-level problem.
Classic example: Fibonacci numbers
- Given n, compute Fn, where
F0 = 0, F1 = 1, and
for n ≥ 2, Fn =
Fn-1 +
Fn-2.
- Not an optimization problem, but it does exhibit
- Recursion:
- by definition!
- Optimal substructure:
- (not applicable).
- Simple subproblems:
- each subproblem is specified by the single value n.
- Overlapping subproblems:
- Fn depends on
Fn-1 and
Fn-2, which depend on
Fn-2 and
Fn-3 (twice) and
Fn-4, etc.
Why not just use recursion?
def fib(n):
if n == 0: return 0
if n == 1: return 1
return fib(n-1) + fib(n-2)
Problem!
fib(5):
fib(4):
fib(3):
fib(2):
fib(1)
fib(0)
fib(1)
fib(2):
fib(1)
fib(0)
fib(3):
fib(2):
fib(1)
fib(0)
fib(1)
- Notice how some calls are evaluated multiple times,
because of overlapping subproblems.
In fact, it can be shown that fib(1)
will be called
an exponential number of times
(as a function of n) — this is called combinatorial explosion.
Solution
- Idea: store "solutions" to subproblems in a table,
so they can be looked up instead of recomputed.
- Table layout depends on problem, but will typically be an array.
- Details of what is stored for each solution matter:
don't want to run out of memory,
so usually don't store complete solution
(relevant for more complicated problems).
- Values are typically computed in a "bottom-up" fashion:
fill in solutions for small subproblems first,
and work our way up to the overall problem.
- In the case of Fibonacci numbers, we get the following algorithm
(pseudocode):
def fib2(n):
L = [0, 1]
for i = 2,3,...,n:
L.append(L[i-2] + L[i-1])
return L[n]
Try it! (1)
- Try the
"Stacks of
Blocks"
problem again.
- Ignore issues of input/output for now:
suppose you already have the data stored
in an appropriate data structure of your choice.
© Copyright 2012–2015 François Pitt
<francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by
François Pitt is licensed under a
Creative
Commons Attribution-ShareAlike 4.0 International License.