23_Dynamic_Programming.pdf
Lecture 23
Dynamic Programming / Memoization
EECS 281: Data Structures & Algorithms
Data Structures & Algorithms
Dynamic Programming
3
Dynamic Programming
• A primary advantage of a typical recursive
algorithm is to divide the domain into
independent sub-problems
• Some recursive problems do not divide
into independent sub-problems
• Use Dynamic Programming (DP)
– Bottom-up
– Top-down
4
Dynamic Programming
Dynamic Programming is applicable if:
• You have a large problem that can be
broken into smaller subproblems
• The subproblems are NOT independent;
the same subproblems recur in the course
of solving the larger problem (hopefully
many times)
5
Dynamic Programming
• Reduce the run time of a recursive
function
– Change complexity class, often from O(cn) to
O(nc)
• Use memory to avoid computing values
which have already been computed
6
Memoization
• This technique is called memoization
(derived from the Latin word
memorandum (to be remembered)
• Different word than “memor ization”
(although they are cognate words)
• This is how Dynamic Programming
works
7
Memoization
• Rewrite function
– On exit:
• Save the inputs and the result
– On entry:
• Check the inputs and see if they have been
seen before
• If they have, just retrieve the result from
memory rather than recomputing it
• Often done with only minor code changes
8
Example: Fibonacci Sequence
Definition
• F(0) = 0; F(1) = 1
• F(n) = F(n – 1) + F(n – 2)
Find F(3)
• F(3) = F(2) + F(1); F(2) = F(1) + F(0)
Þ
• F(3) = (F(1) + F(0)) + F(1) = (1 + 0) + 1
9
Fibonacci: Naïve Implementation
1 uint64_t findFib(uint32_t i) {
2 if (i == 0 || i == 1)
3 return i;
4 return findFib(i – 1) + findFib(i – 2);
5 } // findFib()
• Spectacularly inefficient recursive algorithm
• Exponential running time: O(1.618N)
10
1 #include
2 using namespace std;
3
4 // fib(93) is the largest fib that fits in uint64_t
5 static const size_t MAX_FIB = 93;
6 uint64_t fib(uint32_t n);
7
8 int main() {
9 for (size_t i = 0; i <= MAX_FIB; ++i)
10 cout << "fib(" << i << "): " << fib(i) << endl;
11
12 return 0;
13 } // main()
Fibonacci: Top-Down DP
11
15 uint64_t fib(uint32_t n) {
16 // Array of known Fibonacci numbers. Start out with 0, 1,
17 // and the rest get automatically initialized to 0.
18 // MAX_FIB + 1 used to account for 0-indexing
19 static uint64_t fibs[MAX_FIB + 1] = { 0, 1 };
20
21 // Doesn't fit in 64 bits, so don't even bother computing
22 if (n > MAX_FIB)
23 return 0;
24
25 // Is already in array, so look it up
26 if (fibs[n] > 0 || n == 0)
27 return fibs[n];
28
29 // Currently unknown, so calculate and store it for later
30 fibs[n] = fib(n – 1) + fib(n – 2);
31 return fibs[n];
32 } // fib()
Fibonacci: Top-Down DP
12
Fibonacci: Bottom-Up DP
1 uint64_t fibBU(uint32_t i) {
2 uint64_t f[MAX_N];
3 i = min(i, MAX_N – 1);
4 f[0] = 0;
5 f[1] = 1;
6 for (size_t k = 2; k <= i; k++)
7 f[k] = f[k - 1] + f[k - 2];
8 return f[i];
9 } // fibBU()
• Evaluate function by
– Starting at smallest
function value
– Using previously
computed values at
each step to compute
current value
• Must save all previously
computed values
– Note that the values in
f[] grow exponentially
Simple technique has converted an exponential algorithm
(O(1.618N)) to a linear one (O(n))
13
Example: Binomial Coefficient
Definition:
For ! ≥ # ≥ 0; !,# ∈ ℤ
n
m
!
"
#
$
%
&=
n!
m!(n−m)!
14
Binomial Coefficient
Naïve Approach
• Solve for n! (iteratively or recursively)
– fact(n) = n * fact(n – 1)
• Solve for (n – m)!
• Solve for m!
• Integer overflow is a major issue:
– 13! causes overflow of a 32-bit integer
– 21! causes overflow of a 64-bit integer
– 35! causes overflow of a 128-bit integer
15
Binomial Coefficient Rewritten
Base cases, for ! ≥ 0:
Recursive definition, for ! > # ≥ 1:
n
m
!
”
#
$
%
&=
n−1
m−1
!
”
#
$
%
&+
n−1
m
!
”
#
$
%
&
n
0
!
”
#
$
%
&=
n
n
!
”
#
$
%
&=1
16
Binomial Coefficient: Top-Down
1 uint64_t biCoeffTD(uint32_t n, uint32_t m) {
2 if (m == 0 || m == n)
3 return 1;
4 else
5 return biCoeffTD(n – 1, m – 1)
6 + biCoeffTD(n – 1, m);
7 } // biCoeffTD()
• Elegant? Yes.
• Efficient? NO!
17
Binomial Coefficient: Top-Down
1 uint64_t binomHelper(uint32_t n, uint32_t m,
2 vector
3 if (m == 0 || m == n) {
4 memo[m][n] = 1;
5 return 1;
6 } // if
7 if (memo[m][n] > 0)
8 return memo[m][n];
9 memo[m][n] = binomHelper(n – 1, m – 1, memo)
10 + binomHelper(n – 1, m, memo);
11 return memo[m][n];
12 } // binomHelper()
13
14 uint64_t binomTD(unsigned int n, unsigned int m) {
15 vector
16 return binomHelper(n, m, memo);
17 } // binomTD()
18
Binomial Coefficient: Bottom-Up
1 uint64_t biCoeffBU(uint32_t n, uint32_t m) {
2 vector
3 for (size_t i = 0; i <= m; ++i) {
4 for (size_t j = i; j <= n; ++j) {
5 if ((i == j) || (i == 0))
6 c[i][j] = 1;
7 else
8 c[i][j] = c[i - 1][j - 1]
9 + c[i][j - 1];
10 } // for j
11 } // for i
12 return c[m][n];
13 } // biCoeffBU()
• Base cases: (i == j) and
(j == 0)
• Only finding values for half
of 2D vector (j starts out
equal to i)
• Clearly, algorithm
calculates approx (nm)/2
integers in vector c
• Therefore, is O(nm)
19
General Approach: Top-Down
• Save known values as they are calculated
• Generally preferred because:
– Mechanical transformation of ‘natural’ (recursive)
problem solution
– Order of computing subproblems takes care of itself
– May not need to compute answers to all subproblems
• Adaptive
– Only compute needed subproblems
20
General Approach: Bottom-up
• Precompute values from base case up
toward solution
• Loosely “non-adaptive”
– will compute all smaller cases, needed or not
21
Nuances
• Bottom-up dynamic programming can be used
any time Top-down dynamic programming is
used
• Time and space requirements for dynamic
programming may become prohibitively large
– Memo space used for either approach
– Additional stack space used for top-down approach
– Bottom-up approach can recycle/collapse previous
memo steps
22
Top-Down or Bottom-Up?
• For any problem we’ll give you, either solution
will work (top-down, bottom-up)
• Some problems the base cases are easy to see,
but the ones just above that are hard
• Some problems it’s hard to see which sub-
problems need to be computed
• https://www.quora.com/Can-every-problem-on-Dynamic-
Programming-be-solved-by-both-top-down-and-bottom-
up-approaches
23
Summary: Dynamic Programming
• Advanced technique for difficult problems
• Trading space (when ample) for time
• Applied when solution domains are
dependent upon each other
• Bottom-up
– Iteratively pre-compute all values ‘from the bottom’
• Top-down
– Recursively compute and save needed values ‘from
the top’
Data Structures & Algorithms
Dynamic Programming
Data Structures & Algorithms
DP: Knight Moves
26
Knight Moves
The Knight travels in
an “L” fashion, moving
2 spaces in any
direction, turning 90°
left or right and moving
1 space
27
Knight Moves
• Moving from the top-left corner to bottom-
right corner of a standard 8x8 board can
be done in a minimum of 6 moves
• Q: How could we determine the number of
different ways it could be done, in exactly
6 moves?
• A: Use Dynamic Programming, with a 3D
memo to calculate number of routes to all
possible locations after 6 moves.
28
Knight Moves
Possible after 2 movesPossible after 1 move
Top-Left Corner
Start here
29
Knight Moves
Overlapping sub-problem:
• is reachable after
moving to either
• Calculating a partial path
from to the final
destination could be used
in both complete
solutions through
30
Knight Moves
Memo[0]
1
Memo[1]
1*
1
1
* gray numbers
are previous
memo
(View of upper-left 5x5 sections of a full 8x8 board)
31
Memo[2]
(w/ Memo[1]
in gray)
2 1 1
1 1
1 1 1
1 2
1 1
32
Memo[2] only
2 1 1
1
1 1
1 2
1 1
33
Calculating
Memo[3]:
Location
(1, 2)
is Memo[3]
is Memo[2]
is Memo[2]
(unused)
2 1 1
8 1
1 1
1
2
1 1
8
1
1
34
Calculating
Memo[3]:
Location
(2, 1)
is Memo[3]
is Memo[2]
is Memo[2]
(unused)
2
1
1
8
1
1
1
1
2
1
1
1
8
1
35
Memo[3]
(w/ Memo[2]
in gray)
2 2 1 11
2 8 31
1 8 14
1 1 4 22
1 3 1 2
2
2
4
1
3
2 4 3
2 1
36
Memo[4] only
16 17 18
10 22
17 16 23
22 36
18 23 18
7
8 7
10
14 9
9
8 14
7 10 9
7 9
6 4
6
4
37
Memo[5] only
55 57
55 132 100
132 120
57 120 108
100 108
62 18
64
126 38
66
111 36
62 126 111
64 66
18 38 36
54
54 19
19
38
Memo[6] only
264 407 442
354 603
407 640 720
603 938
442 720 732
264
407 254
435
641 357
456
407 641
264 435 456
254 357
458 250
294
250 108
39
Knight Moves Wrap-up
• What is the time complexity for this solution?
• Generalize time complexity given a board size
(N) and number of moves (M)
• What is the memory complexity?
• How could the memory footprint be reduced?
• Describe the top-down method
Data Structures & Algorithms
DP: Knight Moves