-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dynamic programming
46 lines (28 loc) · 1.79 KB
/
Dynamic programming
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Applies to optimization problems.
transform exponential-time algorithms into polynomial-time algorithms.
Divde-and-conquer, disjoint subproblems
Dynamic programming, subproblems overlap when subproblems share subproblems.
----> apply it to optimization problems!!!!!
4 steps:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from computed information.
Rod cutting problem:
We can cut up a rod of length n in 2^(n-1) different ways, since we have an independent option of cutting, or not cutting.
r(n) = pn + (r(1)+r(n-1) + (r(2)+r(n-2)) +...+ (r(n-1)+r(1))
simplify: r(n) = max(pi+(r(n-i)
recursive top-down implementation:
max(a, p[i]+cut-rod(p,n-i)
it returns the maximum revenue possible for a rod of length n.
This algorithm is so inefficient. The problem is that CUT_ROD calls itself recursively over and over again with the same parameter values;
it solves the same subproblems repeatedly.
Convert it into an efficient algorithm. ---> dynamic programmming.
Dynamic programming thus uses additional memory to save computation time; it serves an example of a time-memory trade-off.
It's bottom-up method!!!!
Time complexity is O(n^2) due to it's double loop.
Matrix-chain multiplication:
Given a chain <A1,A2,...,An> of n matrices, where for i = 1, 2, 3, ... , n Ai has dimention pi-1 * Pi, fully parenthesize the product
A1A2..An in a way that minimizes the number of scalar multiplicatioins.
Typically, the time invested in determining this optimal order is more than paid for by the time saved later on when actually performing
the matrix multiplications (such as performing only 7500 scalar multiplications instead of 75,000).