Introduction to Dynamic Programming: A Powerful Problem-Solving Technique
Dynamic programming (DP) is a bottom-up approach introduced by Richard Bellman in the 1950s. Similar to divide-and-conquer, DP breaks down complex problems into smaller subproblems, solving them methodically and storing solutions in a table for efficient computation. DP is widely used in optimization problems, with key elements including recurrence relations, tables for memorization, and algorithms for filling tables. An example of DP application is demonstrated through Fibonacci numbers and a canoe trip optimization problem.
Uploaded on Sep 19, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Dynamic Programming (DP) Introduced by Richard Bellman in 1950 s. DP is a bottom-up approach. Similar to divide-and-conquer, DP breaks the original problem into smaller problems. DP solves the smallest problems first and then the larger problems. DP is a tabular method. It uses a table to memorize solutions of smaller problems. And then it builds larger solutions from smaller solutions in the table. Typically DP can be applied to optimization problems.
Basic elements of a DP algorithm 1. A DP recurrence, i.e. a recursive relation between larger and smaller solutions. 2. A table for memorizing solutions. 3. An algorithm for filling the table.
Fibonacci Numbers Recursive Fibonacci numbers: Int fib(int n) { if (n<2) return n; else return fib(n 1) + fib(n 2); } DP Fibonacci numbers: 1. fn = fn-1+fn-2 2. Int f[n+1]; /* f[i] contains fi */ 3. The algorithm. f[0] = 0; f[1] = 1; for (i=2; i<=n; ++i) f[i] = f[i-1] + f[i-2];
A Canoe Trip Definition of the problem: There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. For each post i and each downstream post j, the cost of the rental from post I to post j is known. We want to know what is the best way to rent and return canoes from post 0 to post n-1.
Defining subproblems (smaller problems) Define mc(i) as the minimum coast to travel from post 0 to post i. The DP recurrence mc(0) = 0 mc(i) = MIN { mc(j) + cost[j][i]} 0 j<i
The table int mc[n]; // mc[i] contains min cost from post 0 to post i; The algorithm for filling the table mc[0] = 0; for (i=1; i<n; ++i) { mc[i] = cost[0][i]; prv[i] = 0; for (j=1; j<i; ++j) { temp = mc[j] + cost[j][i]; if (temp<mc[i]) { mc[i] = temp; prv[i] = j; } } } i = n-1; while (i>0) { printf("%d <-- ", i+1); i = prv[i]; } printf("%d\n", 0);
Example 1 8 0 Cost 0 1 2 3 4 0 2 3 23 8 4 20 11 24 20 8 0 5 0 5 0 0 mc(i) = MIN { mc(j) + cost[j][i]} 0 j<i 0 0 1 8 0 2 19 1 3 16 1 4 mc prv 21 3 0 1 3 4
Principle of optimality Principle of optimality: Suppose that in solving a problem, we have to make a sequence of decisions D1, D2, , Dn. If this sequence is optimal, then the last k decisions, 1 k n must be optimal. In solving an optimization problem, DP may be used only when the principle of optimality holds.
Matrix Product Chain Review: Matrix Multiplication. C = A*B A is d e and B is e f f B 1 e = k = , [ i C ] , [ i A ] * [ , ] j k B k j j e 0 O(def ) time e A C d i i,j d f
Matrix Product Chain Matrix product chain: Compute A=A0*A1* *An-1 Ai is di di+1 Problem: What is the best order? Example B is 3 100 C is 100 5 D is 5 5 (B*C)*D takes 1500 + 75 = 1575 multiplications B*(C*D) takes 1500 + 2500 = 4000 multiplications
Defining subproblems Define Ni,j as the minimum number of multiplications needed for computing Ai*Ai+1* *Aj. The DP recurrence Ni,j = min {Ni,k +Nk+1,j+didk+1dj+1} i k<j
The table answer N 1 2 1 0 2 j n 0 0 i 0 0 0 0 0 0 n 0 Ni,j = min {Ni,k +Nk+1,j+didk+1dj+1} i k<j
The algorithm for (i=0; i<n; ++i) N[i][i] = 0; for (len=2; len<=n; ++len) { for (i = 0; i<n-len+1; ++i) { j = i + len 1; N[i][j] = ; for (k = i; k<j; ++k) { q = N[i][k] + N[k+1][j] + d[i]*d[k+1]*d[j+1]; if (q < N[i][j]) N[i][j] = q; } } }
Example Ni,j = min {Ni,k +Nk+1,j+didk+1dj+1} i k<j 1 2 3 5 4 7 5 10 6 d 13 18 9 j N 1 2 3 4 5 1 2 3 4 5 810 k=1 1440 k=2 315 0 0 i 0 350 910 0 0
Longest Common Subsequence Problem: Given 2 sequences, X = x1,...,xm and Y = y1,...,yn , find a common subsequence whose length is maximum. springtime ncaa tournament basketball printing north carolina krzyzewski Subsequence need not be consecutive, but must be in order.
Nave Algorithm For every subsequence of X, check whether it s a subsequence of Y . Time: O(n2m). 2msubsequences of X to check. Each subsequence takes O(n)time to check: scan Y for first letter, for second, and so on.
LCS properties Theorem Let Z = z1, . . . , zk be any LCS of X and Y . 1. If xm= yn then zk= xm= ynand Zk-1 is an LCS of Xm-1 and Yn-1. 2. If xm yn then either zk xmand Z is an LCS of Xm-1 and Y. 3. or zk ynand Z is an LCS of X and Yn-1. Notation: prefix Xi= x1,...,xi is the first i letters of X.
Defining subproblems Define C(i, j) as length of LCS of Xi and Yj . We want C(m,n). The DP recurrence 0 if i=0 or j=0, C(i, j) = C(i-1, j-1)+1 if i,j>0 and xi=yj max { C(i-1, j), C(i, j-1)} if i,j>0 and xi yj
The table C 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 j 0 n 0 0 0 0 0 0 0 i,j i answer m 0 if I=0 or j=0, C(I, j) = C(i-1, j-1)+1 if I,j>0 and xi=yj max { C(i-1, j), C(i, j-1) } if I,j>0 and xi=yj
The algorithm for (i=1; i<=m; ++i) C[i][0] = 0; for (j=1; j<=n; ++j) C[j][0] = 0; for (i=1; i<=m; ++i) { for (j=1; j<=n; ++j) { if (xi == yj) { C[i][j ] = C[i 1][j 1] + 1; B[i, j ] = } else { if (C[i 1][j] C[i][j 1]) { C[I][j] = C[i 1][j]; B[i][j] = ; } else { C[i][j] = C[i][j 1]; B[i][j] = ; } } } } B[i][j] points to the entry whose subproblem we used in solving LCS of Xi and Yj. Time: O(mn)
Finding LCS j 0 1 2 3 4 5 Yj B D i C A B Xi 0 0 0 0 0 0 0 A 0 0 0 0 1 1 1 B 2 0 1 1 1 1 2 C 3 0 1 1 2 2 2 B 4 0 1 1 2 3 2
Finding LCS j 0 1 2 3 4 5 Yj B D i C A B Xi 0 0 0 0 0 0 0 A 0 0 0 0 1 1 1 B 2 0 1 1 1 1 2 C 3 0 1 1 2 2 2 3 B 4 0 1 1 2 2
0-1 Knapsack: an example Weight Value vi wi Objects 2 3 This is a knapsack Max weight: W = 20 3 4 4 5 5 8 9 10
0-1 Knapsack problem Given a knapsack with maximum capacity W, and a set of n objects. Each object i has a weight wi and a value vi(all wi , viand W are integer values). Problem: How to pack the knapsack to achieve maximum total value of packed objects?
0-1 Knapsack problem The problem, in other words, is to find: max vi subject to wi W i Ti T 1. The problem is called a 0-1 problem, because each object must be entirely accepted or rejected. 2. Just another version of this problem is the Fractional Knapsack Problem , where we can take fractions of objects.
Brute-force approach Since there are n items, there are 2n possible combinations of items. We go through all combinations and find the one with the most total value and with total weight less or equal to W. Running time will be O(n2n).
The DP approach Can we do better? Yes, with an algorithm based on dynamic programming. We need to identify the subproblems. Defining subproblems Define V(k,w) as the maximum total value if we only include objects 1 to k and if the capacity is w.
The DP recurrence V(k-1, w) if wk >w V(k,w) = max{V(k-1, w), V(k-1, w-wk)+vk} The table V 0 1 0 1 2 w W K-1,w-wk K-1,w k k,w answer n
The algorithm for filling the table for (w=0; w<=W; ++w) P[0][w] = 0; for (i=0; i<=n; ++i) { P[i][0] = 0; for (w=0; w<=W; ++w) if (wi <= W) /* object i can be included */ if (pi+P[i-1][w-wi]>P[i-1][w]) P[i][w] = pi + P[i-1][w- wi]; else P[i][w] = P[i-1][w]; else P[i][w] = P[i-1][w]; }
Optimal Binary Search Trees Problem Given sequence K = k1< k2< < kn of n sorted keys, with a search probability pifor each key ki. Want to build a binary search tree (BST) with minimum expected search cost. Actual cost = # of items examined. For key ki, cost = depthT(ki)+1, where depthT(ki)= depth of kiin BST T .
Expected Search Cost search [ cost in ] E T n = n = + ( depth ( ) ) 1 k p T i i 1 i n = i = i = + depth ( ) k p p T i i i 1 1 n = i = + 1 depth ( ) k p T i i Sum of probabilities is 1. 1
Example 1 Consider 5 keys with these search probabilities: p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3. k2 i depthT(ki) depthT(ki) pi 1 1 0.25 2 0 0 3 2 0.1 4 1 0.2 5 2 0.6 1.15 k1 k4 k3 k5 Therefore, E[search cost] = 2.15.
Example 2 p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3. k2 i depthT(ki)depthT(ki) pi 1 1 0.25 2 0 0 3 3 0.15 4 2 0.4 5 1 0.3 1.10 k1 k5 k4 Therefore, E[search cost] = 2.10. k3 This tree turns out to be optimal for this set of keys.
Observations: Optimal BST may not have smallest height. Optimal BST may not have highest-probability key at root. Build by exhaustive checking? Construct each n-node BST. For each BST, compute expected search cost. But there are O(4n/n3/2)different BSTs with n nodes.
Some properties of optimal BST One of the keys in ki, ,kj, say kr, where i r j, must be the root of an optimal subtree for these keys. Left subtree of krcontains ki,...,kr 1. Right subtree of krcontains kr+1, ...,kj. kr To find an optimal BST: Examine all candidate roots kr, for i r j Determine all optimal BSTs containing ki,...,kr 1 and containing kr+1,...,kj ki kr-1 kr+1 kj
Defining subproblems Define e(i, j ) as expected search cost of optimal BST for ki,...,kj. The DP recurrence 0 if j=i-1, e(i, j) = min { e(i, r-1)+e(r+1, j)+w(i,j)} if i j i r j j = l = ( , ) w i j lp i
The table answer e 1 2 0 0 1 j n 0 0 i 0 0 0 0 0 0 n+1 0 0 if j=i-1, e(i, j) = min { e(i, r-1)+e(r+1, j)+w(i,j)} if i j i r j
The algorithm for (i=1; i<= n+1; ++i) e[i][i 1] = w[i][i 1] = 0; for (l=1; l<=n; ++I) { for (i=1; i<=n l+1; ++i) { j i + l 1; e[i][j] = ; w[i][j] = w[i][j 1] + pj; for (r=i; r<=j; ++r) { t = e[i][r 1] + e[r+1][j ] + w[i][j]; if (t<e[i][j]) { e[i][j ] = t; root[i][j ] = r; } } } }
Home works 1. Complete the table on slide 14. 2. Given an array A of nonnegative integers such that A[i] represents the max number of steps that can be made forward from A[i]. Design a DP algorithm to determine how to use the minimum number of jumps to reach the end of the array A starting from A[0]. If A[i] is 0, then we cannot move through A[i]. Example: If A[] = {1, 3, 0, 8, 4, 2, 6, 7, 6, 8, 0}, the output is 3 (A[0] A[1] A[3] A[10]). A[0] is 1, so can only go to A[1]. A[1] is 3, so can make at most 3 steps i.e. to A[2] or A[3] or A[4].
