6.006 Introduction to Algorithms, Lecture 16: Dynamic Programming Subproblems

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 16: Dyn. Prog. Subproblems Lecture 16: Dyn. Prog. Subproblems Dynamic Programming Review • Recursion where subproblem dependencies overlap, forming DAG • “Recurse but re-use” (Top down: record and lookup subproblem solutions) • “Careful brute force” (Bottom up: do each subproblem in order) Dynamic Programming Steps (SRT BOT) 1. Subproblem definition subproblem x 2 X • Describe the meaning of a subproblem in words, in terms of parameters • Often subsets of input: prefixes, suffixes, contiguous substrings of a sequence • Often multiply possible subsets across multiple inputs • Often record partial state: add subproblems by incrementing some auxiliary variables 2. Relate subproblem solutions recursively x(i) = f (x(j), . . .) for one or more j < i • Identify a question about a subproblem solution that, if you knew the answer to, reduces the subproblem to smaller subproblem(s) • Locally brute-force all possible answers to the question 3. Topological order to argue relation is acyclic and subproblems form a DAG 4. Base cases • State solutions for all (reachable) independent subproblems where relation breaks down 5. Original problem • Show how to compute solution to original problem from solutions to subproblem(s) • Possibly use parent pointers to recover actual solution, not just objective function 6. Time analysis P • x2X work(x), or if work(x) = O(W ) for all x 2 X, then |X| · O(W ) • work(x) measures nonrecursive work in relation; treat recursions as taking O(1) time 2 Lecture 16: Dyn. Prog. Subproblems Longest Common Subsequence (LCS) • Given two strings A and B, find a longest (not necessarily contiguous) subsequence of A that is also a subsequence of B. • Example: A = hieroglyphology, B = michaelangelo • Solution: hello or heglo or iello or ieglo, all length 5 • Maximization problem on length of subsequence 1. Subproblems • x(i, j) = length of longest common subsequence of suffixes A[i :] and B[j :] • For 0  i  |A| and 0  j  |B| 2. Relate • Either first characters match or they don’t • If first characters match, some longest common subsequence will use them • (if no LCS uses first matched pair, using it will only improve solution) • (if an LCS uses first in A[i] and not first in B[j], matching B[j] is also optimal) • If they do not match, they cannot both be in a longest common subsequence • Guess whether A[i] or B[j] is not in LCS ⇢ x(i + 1, j + 1) + 1 • x(i, j) = max{x(i + 1, j), x(i, j + 1)} if A[i] = B[j] otherwise • (draw subset of all rectangular grid dependencies) 3. Topological order • Subproblems x(i, j) depend only on strictly larger i or j or both • Simplest order to state: Decreasing i + j • Nice order for bottom-up code: Decreasing i, then decreasing j 4. Base • x(i, |B|) = x(|A|, j) = 0 (one string is empty) 5. Original problem • Length of longest common subsequence of A and B is x(0, 0) • Store parent pointers to reconstruct subsequence • If the parent pointer increases both indices, add that character to LCS Lecture 16: Dyn. Prog. Subproblems 6. Time • # subproblems: (|A| + 1) · (|B| + 1) • work per subproblem: O(1) • O(|A| · |B|) running time 1 2 3 4 5 6 7 8 9 10 def lcs(A, B): a, b = len(A), len(B) x = [[0] * (b + 1) for _ in range(a + 1)] for i in reversed(range(a)): for j in reversed(range(b)): if A[i] == B[j]: x[i][j] = x[i + 1][j + 1] + 1 else: x[i][j] = max(x[i + 1][j], x[i][j + 1]) return x[0][0] 3 4 Lecture 16: Dyn. Prog. Subproblems Longest Increasing Subsequence (LIS) • Given a string A, find a longest (not necessarily contiguous) subsequence of A that strictly increases (lexicographically). • Example: A = carbohydrate • Solution: abort, of length 5 • Maximization problem on length of subsequence • Attempted solution: – Natural subproblems are prefixes or suffixes of A, say suffix A[i :] – Natural question about LIS of A[i :]: is A[i] in the LIS? (2 possible answers) – But then how do we recurse on A[i + 1 :] and guarantee increasing subsequence? – Fix: add constraint to subproblems to give enough structure to achieve increasing property 1. Subproblems • x(i) = length of longest increasing subsequence of suffix A[i :] that includes A[i] • For 0  i  |A| 2. Relate • We’re told that A[i] is in LIS (first element) • Next question: what is the second element of LIS? – Could be any A[j] where j > i and A[j] > A[i] (so increasing) – Or A[i] might be the last element of LIS • x(i) = max{1 + x(j) | i < j < |A|, A[j] > A[i]} [ {1} 3. Topological order • Decreasing i 4. Base • No base case necessary, because we consider the possibility that A[i] is last 5. Original problem • What is the first element of LIS? Guess! • Length of LIS of A is max{x(i) | 0  i < |A|} • Store parent pointers to reconstruct subsequence Lecture 16: Dyn. Prog. Subproblems 5 6. Time • # subproblems: |A| • work per subproblem: O(|A|) • O(|A|2 ) running time • Exercise: speed up to O(|A| log |A|) by doing only O(log |A|) work per subproblem, via AVL tree augmentation 1 2 3 4 5 6 7 8 def lis(A): a = len(A) x = [1] * a for i in reversed(range(a)): for j in range(i, a): if A[j] > A[i]: x[i] = max(x[i], 1 + x[j]) return max(x) 6 Lecture 16: Dyn. Prog. Subproblems Alternating Coin Game • Given sequence of n coins of value v0 , v1 , . . . , vn 1 • Two players (“me” and “you”) take turns • In a turn, take first or last coin among remaining coins • My goal is to maximize total value of my taken coins, where I go first • First solution exploits that this is a zero-sum game: I take all coins you don’t 1. Subproblems • Choose subproblems that correspond to the state of the game • For every contiguous subsequence of coins from i to j, 0  i  j < n • x(i, j) = maximum total value I can take starting from coins of values vi , . . . , vj 2. Relate • I must choose either coin i or coin j (Guess!) • Then it’s your turn, so you’ll get value x(i + 1, j) or x(i, j 1), respectively • To figure out how much value I get, subtract this from total coin values P P • x(i, j) = max{vi + jk=i+1 vk x(i + 1, j), vj + jk=i1 vk x(i, j 1)} 3. Topological order • Increasing j i 4. Base • x(i, i) = vi 5. Original problem • x(0, n 1) • Store parent pointers to reconstruct strategy 6. Time • # subproblems: ⇥(n2 ) • work per subproblem: ⇥(n) to compute sums • ⇥(n3 ) running time • Exercise: speed up to ⇥(n2 ) time by precomputing all sums via dynamic programming (!) Pj k=i vk in ⇥(n2 ) time, Lecture 16: Dyn. Prog. Subproblems 7 • Second solution uses subproblem expansion: add subproblems for when you move next 1. Subproblems • Choose subproblems that correspond to the full state of the game • Contiguous subsequence of coins from i to j, and which player p goes next • x(i, j, p) = maximum total value I can take when player p 2 {me, you} starts from coins of values vi , . . . , vj 2. Relate • Player p must choose either coin i or coin j (Guess!) • If p = me, then I get the value; otherwise, I get nothing • Then it’s the other player’s turn • x(i, j, me) = max{vi + x(i + 1, j, you), vj + x(i, j • x(i, j, you) = min{x(i + 1, j, me), x(i, j 3. Topological order • Increasing j i 4. Base • x(i, i, me) = vi • x(i, i, you) = 0 5. Original problem • x(0, n 1, me) • Store parent pointers to reconstruct strategy 6. Time • # subproblems: ⇥(n2 ) • work per subproblem: ⇥(1) • ⇥(n2 ) running time 1, me)} 1, you)} 8 Lecture 16: Dyn. Prog. Subproblems Subproblem Constraints and Expansion • We’ve now seen two examples of constraining or expanding subproblems • If you find yourself lacking information to check the desired conditions of the problem, or lack the natural subproblem to recurse on, try subproblem constraint/expansion! • More subproblems and constraints give the relation more to work with, so can make DP more feasible • Usually a trade-off between number of subproblems and branching/complexity of relation • More examples next lecture