CS计算机代考程序代写 data structure algorithm 23_Dynamic_Programming.pdf

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> &memo) {
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> memo(m + 1, vector(n + 1));
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> c(m + 1, vector(n + 1));
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