16. Dynamic Programming, Part 2: LCS, LIS, Coins

All right, welcome back to 006 Dynamic Programming. We're now in step two out of four, going to see a bunch more examples, three more examples of dynamic programming, longest common subsequence, longest increasing subsequence, and kind of a made up problem from 006 alternating coin game. And through those examples we're going to explore a few new ideas, things we haven't seen in action before yet. Dealing with multiple sequences instead of just one. Dealing with substrings of sequences instead of prefixes and suffixes, parent pointers. So we can recover solutions like in shortest paths. And a big one, which will mostly be fleshed out in the next lecture, is subproblem constraint and expansion. This is all part of the sortbot paradigm. Remember, sub problems, relations, topological order, base case, original problem and time. Here is sub problems and relations. I've written down both what these things are and the sort of key lessons we got from the first dynamic programming lecture. Namely, we want to split up our problem into multiple sub problems. And if your input is a sequence, that's the main case we've seen so far, like the bowling problem, for example. Then the natural sub problems to try are prefixes, suffixes or substrings. Prefixes and suffixes are nice because there's few of them. There's only a linear number of them. In general, we want a polynomial number. Sometimes you can get away with one of these. They're usually about the same. Sometimes you need substrings. There's quadratically many of those. Then once you set up the subproblems, which it's easy to set up sub problems but hard to do it right. To test whether you did it right is can I write a recurrence relation that relates one subproblem solution to smaller subproblems solutions? And the general trick for doing this is to identify some feature of the solution you're looking for. So you're trying to solve some sub problem and you try to ask a question whose answer would let you reduce to a smaller sub problem. So if you can figure out what that question is, and that question only has a polynomial number of answers, then boom, and you've only got polynomial number of sub problems, then you will get a polynomial running time. So I have, I think another way to say this. We just locally brute force all possible answers to whatever question we come up with as long as there's polynomially many. And then each of them is going to recursively call the smaller sub problems. But because we memoize, we'll only solve each sub problem once. And so in the end, the running time will be at most the number of sub problems times the non recursive work done in that relation. For that to work, of course, the relations between sub problems must be acyclic. So we like to give an explicit topological order. Usually it's a couple of for loops, but this is a topological order in the sub problem dag, which I defined somewhat informally last time. But the vertices are sub problems, and I want to draw an edge from a smaller problem to a bigger problem, meaning that if evaluating B in this relation calls A, then I'll draw an arrow from A to B from the things I need to do first to the things I'll do later. So then topological order will be ready. By the time I try to compute B, I will have already computed A. And of course the relation also needs base cases. And then sometimes the original problem we want to solve is just one of those sub problems. Sometimes we need to combine multiple. We'll see that today. So that's review of this framework and let's dive into longest common subsequence. This is kind of a classic problem. It even has applications to things like computational biology. You have two DNA sequences. You want to measure how in common they are. One version of that, you might see other versions in recitation called edit distance. This is sort of a simplest, cleanest version where I give you two sequences. I have two examples, an example here. So for example, it could be a sequence of letters. So my first sequence spells hieroglyphology study of hieroglyphs. And second sequence spells Michelangelo. And what I'd like is a subsequence. So remember, substring has to be some continuous range, some interval subsequence. You can take any subset of the letters in your sequence or any subset of the items in your sequence. So you can have blanks in between, you can skip over items. And so what we want is the longest sequence, that is a subsequence of both the first sequence string, the first sequence and the second string. And if you stare at this long enough, the longest common subsequence, I don't think it's unique, but there is a longest common subsequence, which is hello hiding in there. And that is a longest common subsequence. So given that input, the goal is to compute hello or whatever the longest common subsequence is. So we're given. Write this down carefully. Given two sequences, let me name them A and B. We want to find the Longest sequence L. That's a subsequence of, of both A and B. So that's the problem definition and we're going to see how to solve it using dynamic programming. And whereas in the bowling problem we just had a single sequence of numbers, the values of the bowling pins, here we have two sequences. And so we need a new trick. Before we said, ok, if our subproblems, or, sorry, if our input consists of a single sequence, we'll try prefixes, suffixes or substrings. Now we've got two sequences, so somehow we need to combine multiple inputs together. And so here's a general trick, subproblems for multiple inputs. It's a very simple trick. We just take the product, multiply the sub problem spaces. In the sense of cross product of sets, and in particular from an accommodatorial perspective. So we have sort of two inputs, the first sequence A and the second sequence B. For each of them there's a natural choice or there's three natural choices. We could do one of these. I will choose suffixes for A and suffixes for B. You could do some other combination, but that would be enough for here. And then I want to multiply these spaces, meaning the number of sub problems is going to be the product of the number of suffixes here times the number of suffixes here. And in other words, every sub problem in LCS is going to be a pair of suffixes. So let me write that down. So for lcs, our sub problems. Are L of ij. This is going to be the longest common subsequence of the suffix of A starting at I and the suffix of B starting at J. And just to be clear how many there are, I'll give the ranges for I and J. I'm not going to assume the sequences are the same length like in the example. So I'll write lengths of A and lengths of B. I like to include the empty suffix. So when J equals the length of B, that's zero items in it, because that makes for really easy base cases. So I'd like to include those in my sub problems. So that was the S in sortbot. Now I claim that that set of subproblems is enough to do a relation, recursive relation among them. So I'd like to solve every sub problem lij and relation is actually pretty simple, but it's maybe not so obvious. So the idea is, because we're looking at suffixes, we should always think about what happens in the first letter, because if we remove that first letter, then we get a smaller suffix. If you're doing prefixes, you should always look at the last letter. Either one would work for this problem. So we're doing suffixes. So we look at A of I and we look at B of J. That's the first letter in the suffix A starting at I and the suffix B starting at J. And there are two cases. They could be equal or different. I think the easier case to think about is when they're different. So like in Hieroglyphology and Michelangelo, if we look at the whole string, say the first letter in the top one is H. The first letter in the second one is M. Those are different letters. So clearly one of those letters is not in the common subsequence because they don't match. I can't start with an H. I can start with an H. I could start with an M, but I can't start with both. One of those letters is not in the output. In this example, it's M, but I don't know which one. So I have this question. I want to identify some question. The question is, do I know that the H is not in the answer, or do I know that M is not in the answer? The final longest common subsequence, we don't know which, so we'll just try both. And then we're trying to maximize the length of our common subsequence. So we'll take the max of li +1 j and l I j +1. So the intuition here is one of at least one of AI and bj is not in. The LCS get this wrong. J +1. Sorry, thinking about substrings already. Yeah. These are the beginning points, so I want to exclude the ith letter. So if AI is not in, then I want to look at the suffix starting at I +1. If BJ is not in, then I want to look at the suffix starting at J +1. So the indices are always increasing in the function calls. And the other case is that they're equal. So this one I have a little bit harder time arguing. I'm going to write the answer and then prove that the answer is correct. Here I claim you don't need to make any choices. There's no question you need to answer. You can actually guarantee that AI and BJ might as well be in the longest common subsequence. And so I get one point for that, and then I recurse on all the remaining letters. So from I plus one on and from j plus one on, why Is this ok? Well, we have a B. We're starting at position I and starting at position J for B. And think of some optimal solution, some longest common subsequence, so it pairs up letters in some way. This would be some non crossing pairing between equal letters. And let's say. So first case is that maybe I and J aren't paired with anything. Well that's silly because if they're not paired with anything, you have some pairing on the rest of the items. You can add this pair and that would be a longer subsequence. So that would be a contradiction if we're imagining some hypothetical optimal solution. It has to pair one of these with something. Maybe it pairs I with something else though. Well, if we have a longest common subsequence that looks like that, I can just instead pair I with bj. That still, if I had this pairing, I'm actually not using any of these letters, so why don't I just use this letter instead? So you can argue there is a longest common subsequence that matches AI with bj. And so then we can guarantee by that little proof that we get one point for matching them up and we don't have to max this with anything. So two cases, pretty simple formula. And then we're basically done. We just need to fill in the rest of sortbot. So next is topological order. So this I'll write as for loops, Because I'm dealing with suffixes. We want to start with the empty suffixes and then work our way to larger and larger suffixes. So this might seem backwards. If you're doing prefixes, they would be in increasing order. There's all sorts of orders. You could flip the I and J. It's very symmetric, so it doesn't really matter. But anything that's generally decreasing in I and J is good. Then we have base cases. These are when one of the sequences is empty. I don't care how many items are in B. But if A has no items, there's no common subsequence. I mean it's empty and same for no matter how big A is. If I've exhausted the B string I start from beyond the last item, then I should get zero. Then the original problem we want to solve is L00. That's just longest common subsequence of the entire A and the entire B and time. Okay, so for time we need to know how many sub problems there are. It's A plus one times B plus one. I'll just call that theta ab. Assume these are Non empty subsequences. So this is the number of sub problems. And then what we care about is how much time do we spend for each sub problem in evaluating this recurrence relation. So, so we ignore the cost to recursively call these Ls because they are smaller subproblems. They're already dealt with when I multiply by the number of subproblems. So I just care about this max computation and this equality check. And we'll say those each cost constant time. So this is. Quadratic time. If the two strings are size N, this is N squared general, it's the product of the two string sizes and that's longest common substring. So pretty straightforward. This really doesn't. Other than this little argument understanding the case when they're equal, the easy case when they're unequal, we just try the only two things we could do, one of AI and BJ is not in the longest common subsequence. So what I like to say is we guess which of those is the correct one that is not in the longest common subsequence. And if we guess that it's in A, then we'll recurse on that side. If we guess that it's in J, then we'll recurse by increasing j. And then I'd like to assume, not really that we always make the correct guess, that we made the correct choice whether it's I or j. Now, we don't actually know how to do that. So instead we brute force, we try both of them and then because we're trying to maximize, we take the max. Just another way of thinking about it, but overall very straightforward. The only added complication here is we had to deal with two sequences simultaneously and we just took the product of those. Pretty easy. In general, if you have some constant number of sequences, you can afford to do this, you'll still get polynomial. But of course, once you go to N sequences, you can't afford this. You get like an N to the N behavior. So that's kind of a limit to how far you could go. Two sequences is fine, three sequences is fine, but N sequences. There probably is no polynomial time algorithm for this problem. Cool. I wanted to show you an example. I have an example here. I didn't want to draw hieroglyphology versus Michelangelo, so I came up with another example. Their habit is to say hi. So the longest common subsequence of their and habit is hi. And I mean it's a giant. Well, not that giant. It's. It Looks kind of like a grid graph. The base cases are out here because those correspond. So when I say this, each of these nodes is a sub problem and this corresponds to what is the longest common subsequence between EIR and Abbott. And it should be I. It's the only letter they have in common. And that's why there's a one here, to say that the longest common subsequence has a one has size one. The base cases are when either there has been emptied or when habit has been emptied. So those all have zeros on the outside. And then the problem we care about is this one. It's there versus habit. Claim is the length is two. And what I've drawn in here are what I'll call parent pointers, like we talked about with bfs and shortest paths and so on. This is. So we had this choice. Sometimes we had a choice on whether we recursed here or recursed here was the best thing to do. And so I'll draw in red the arrow from lij. Sorry, to lij from one of these in this case. And in this case there's no choice, but I'll still draw in red that arrow. So these diagonal edges are exactly the cases where the letters match Here, H equals H, I equals I here. So I draw this diagonal edge. That's that first case where the letters are equal. And so I recurse by increasing I and J. That's why I get a diagonal edge. There's also one over here where T equals T. So for Those we're getting a 1 plus you see, this one is 1 larger than the 0. This 2 is 1 larger than the 1. This one is 1 larger than the 0. And for every other vertex we are recursing this way. And this way we see what those two numbers are and we take the max. So this whole diagram is just filled in. For each position where they're not equal, we look at the guy below, we look at the guy to the right. Those are the slightly smaller substrings. We look at those values, we take the max. As long as you compute this in a generally right to left and bottom up fashion. Whenever you're trying to compute a guy, you will have its predecessors already computed. That's the topological order of this graph. And then at the end we get our answer, which is 2. And now if we pay attention to where we came from. For example, this vertex had to come from this direction. Two is the max of two and one. So I highlight the two edge and if I follow this path there should be a unique path to some base case. We don't know which one. And in this case, the diagonal edges correspond to my matching letters. So there's the H here followed by the I here. And so high is our longest common substring. In general, we just follow these pointers backwards, the red pointers, and we get. So not only do we compute the length of the LCs, but we actually can find the LCs using parent pointers. So this is. And this is a concept you can use in most dynamic programs, including all the ones from today. Okay, any questions about LCs? All right, perfectly clear to everyone in the audience. So we move. Oh yeah, now we move on to longest increasing subsequence, which. Did I lose a page here? I just disordered them. Okay. This problem has almost the same name, but is quite different in behavior. Longest increasing subsequence. LIS instead of lcs. Both famous problems. Examples of dynamic programming. Here we're just given one sequence, like carbohydrate. So this is a sequence of letters. And I want to find the longest subsequence of this sequence that is increasing, strictly increasing, let's say. So in this case alphabetically. So I could include cr, for example, but not cb. That would be a descending subsequence. And in general, or in this example, the right answer, or a right answer is abort. There aren't very many English words that are increasing, but there are some and I looked through all of them as I just implemented this dynamic program we're about to write down. It took me like two minutes to write down the DP and then more work to read the dictionary and look for examples. So in general we're given some sequence A. And we want to find the longest increasing subsequence of A, the longest sequence that is increasing strictly. We could use the same thing to solve not strictly increasing, but. So here things are going to be a little trickier. It's easy in that we just have a single sequence. So again we think, ok, let's look at our chart here. We could try prefixes, suffixes or substrings. I personally prefer suffixes. JSON prefers prefixes. Whatever you prefer is fine, but I'll generally start there because there's nothing in this problem that makes me think I need to define, delete things from both ends. One question. Yeah, question. Isn't the answer to this problem always 26? So if. Is the answer always at most 26? Yes, if you're dealing with English words. So when I say sequence Here, this is a sequence of arbitrary integers, word size integers. So there you can have a ton of variety. This is just for the fun of examples, I've drawn this. But even if the answer is 26, finding that longest common subsequence is. You know, the obvious algorithm would be to take all substrings of size 26, which is like n to the 26. So that's we're going to do much faster than that here N squared time. And then if you remove the strictly increasing, then it can be arbitrarily large. Ok, so let's try to do this. Maybe I won't be so pessimistic to write attempt here, let's just go for it. So I want some sub problems and I'm going to choose suffixes. So I'm going to define l of I to be the longest increasing subsequence of the suffix of A, starting at I. That's the obvious thing to do. And now I'm going to leave myself a little space and then I'd like a relation on these. So I'd like to say what L of I is and what do I have to work with? Well, I have L of things larger than I. Those would be smaller suffixes. But let's go back to what is a question that I could ask about this sub problem that might help me figure out what the longest increasing subsequence looks like. So we're looking at a. Here's A from I on longest increasing subsequence is sub subsequence and we'd like to remove letter I. Now when we do that there are two choices. Maybe I is in the longest increasing subsequence or it's not in. So the question I would like to answer is is I in the longest increasing subsequence of a of A? From I onwards this is a binary question. There are two options. So again, just like before and so I can brute force those two options the trouble and then I want the longest one. So I'm going to take the max. So I'd like to take the max of something like li +1. So in the case that I don't put I in the solution that that's fine, then I just look at I +1 on and recursively compute that and that would be my answer. And the other option is that I do put I in the longest increasing subsequence. So I do 1 the rest li 1. If I close this brace, this would be a very strange recurrence because this is always bigger than this one. So there's something wrong here. And the something wrong is I haven't enforced increasing at all. There's no constraints here. It's just saying, well, I'll put I in and then I'll do whatever remains and I'll pray that that's increasing. Probably won't be, because indeed if I is a letter or is a number that is strictly greater than I +1, then this will be wrong. So I really can't always do this. I need to somehow know. I could check whether I +1 is in the answer, but I don't know maybe I +1. So I can check whether the letter I is less than the letter I plus one. But maybe I put this in the longest increasing subsequence and then I put this in the longest increasing subsequence. And so I need to compare these two items, but I don't know when that's going to happen. Things seem really hard. And indeed there's no way from this sub problem definition to write down a relation. But there is a slight tweak to this definition that makes it work. So the trouble we have here, and this is the idea of sub problem constraints or conditions. The trouble we have is when we recursively compute the longest increasing subsequence on the remainder, we don't know the first item in that answer. Maybe it's I plus one, maybe it's some guy over here. If we knew who it was, then we could compare that item to item I. And so what we'd like to do is add a constraint to this sub problem that somehow lets us know where the longest increasing subsequence starts. So what I would like to say is longest increasing subsequence of that suffix that starts with a of I. So in other words, it includes a of I. Okay, this was a separate question. Okay, this is a bit of a funny constraint. It changes the problem. It's no longer what we want to solve. If you think about the original problem before it was solving L of 0. We just want the longest increasing subsequence of the whole thing. Now it's not necessarily L of 0. L of 0 means what is the longest increasing subsequence of the whole sequence? A that includes the first letter of A. And maybe we do include the first letter of A. Maybe we don't. We don't know where the longest increasing subsequence starts. Here, for example, it didn't. It started at the second letter. But conveniently it's OK that We don't know because that's just another question we could ask is where do we start? Where might the LIS start? At the first letter, second letter, third letter. There's only N choices and let's just take the max of all of them. So before I get to the relation, let's solve this problem. I just want the max of l of I for all I. I guess we've been writing size of A here, the maximum will be the overall longest increasing subsequence. So if I could find longest increasing subsequence that includes the first letter or the longest one that includes the second letter, and so on. So it starts at the first letter, starts at the second letter, then this max will be the longest overall. So this sub problem is not what I really wanted, but it's still good enough because it lets me solve my original problem. And this is adding an extra constraint to my sub problem. And doing this is challenging. Thinking about what? The right constraint that would let you solve your problem is tricky, especially in the beginning. But for now let's just take this as a thing that works. Why does it work? Because now I can say, well, this term was fine max. So I'm trying to write longest increasing subsequence starting with the ith letter versus yeah, actually no, this is just going to be different. Ok, so now I get to the central issue, which is I know by the definition of l of I that I include letter I. This, this is going to be in my longest increasing subsequence. That's what I'm looking for by this definition. But I don't know what the second letter is. Could be I plus one, could be I plus two, could be anything bigger. Whenever there's something I don't know, I'll just brute force it. I don't care that I don't know, I'll just take a max over all the possible choices. Let's say that the next letter included in the longest increasing subsequence I is J. Then I would like to look at L of J. Now I don't know what J is, but I'll just brute force all possible choices for J. So it's going to be I strictly less than J because I don't want to include the same letter I again. And otherwise I would get an infinite recursive loop if I put less than or equal to here. And maybe I don't do anything else up to N and ok, not quite done. Now this is the interesting part. I can enforce increasing because I can't just choose any letter J to the right of I. Also the number or letter that's written in here has to be greater than the number that's written here. That's the strictly increasing property. So I can add as a constraint in this max to say A of I is strictly less than A of j. And if you wanted non strictly increasing you would add an equal there. This is mathematical notation in Python. You would say max open paren of this thing for j in this range. If this holds. So I'm just doing the for loop. But I only look at the possible choices for J when the strict increasing property holds and then when that holds I check this. Now this set might be empty. I need to define what the max is when it's empty, then I will just say oh, I also need a one plus, don't I? Let me just do one plus. So we're told that I is in the answer, so we always get one. And then the remainder is this or zero. If there are no AJ's greater than AI, then we'll default to zero and say I is the only item in my increasing subsequence. Okay, so there are a few details to get right, but in general, once you figure out what these recurrences look like, they're very simple. I mean this is one line of code. And then all you need in addition to this is the original sub problem and some other things. We need the base cases, but I should do them in order to Topological order is just the usual for loop. Because I'm doing suffixes, it's going to be I equals length of a down to zero. Base case is going to be l of length of A which is zero because there's no letters in that suffix. And we already did. Okay, and then time. This is a little different from the past examples. So number of sub problems, just like usual is linear length of a sub problems. It's only one sequence we're thinking about now, unlike the previous example. But the work we're doing in this relation now is non trivial work. Before we were just guessing among two different choices. Now we're guessing among up to n different choices. This n here is length of A and so we have theta length of a. Non recursive work. That we're doing in each sub problem. Or you might think of this as choices that we're considering and for each choice we're just spending, I mean we're just taking a max of those items, adding one. So that's a constant overhead. And so we just get this product, which is A squared. Cool. So that's longest increasing subsequence. Make sure I didn't miss anything else. So we're using this idea of asking a question and guessing or brute forcing the answer to that question in two places. One place is we're promising, we're requesting that the longest increasing subsequence starts at I. So then the question is, well, what is the very second item that's in the longest increasing subsequence that it starts with I? We're calling that J. And we're brute forcing all the possible choices that j could be, which conveniently lets us check, confirm that it's actually an increasing subsequence locally from I to J. And then L of J will take care of the rest. By induction, the rest of the longest increasing subsequence starting at J will, will also be increasing. And so this guarantees by induction the whole thing will be increasing. Then we also use this local brute force to solve the original problem because we added this constraint of starting at I, but we didn't actually know overall where to start. But that's fine because there's only eight choices. So I should mention in the running time analysis, so there's solving the sub problems, that's fine. But then there's also a plus whatever it costs to solve the original problem. But that's ok, that's length of A. So this was all of this plus. Length of A is still length of A squared. But if you're doing exponential work here, that would be bad. We have to do some reasonable amount of work to solve the original problem. In terms of all the sub problems, I have an example hiding here. This is a little harder to stare at. Here I have empathy, and this example doesn't have much empathy because the longest increasing subsequence of empathy is empty. Empty is one of the few English words that's increasing. And the hard part here is drawing the dag. It's almost the complete graph, but we only draw edges from smaller letters to bigger letters. So we draw from E to M, from E to P, from E not to A. There's no edge from E to A, from E to T, not from E to H, but yes, from E to Y. And then we also draw from E to the base case, which is there's no more letters. That edge to the base case is corresponds to this 0 or I guess this N where we say ah, let's just recurse, let's just throw away. Actually maybe we don't need the union zero. There in fact, because we include l of N, which is the empty substring, then the definition of L is a little funny. What does it mean to say you start with A of n? You have to define A of N. Right? A of N is not defined, so that's not so nice. So maybe I'll fix that and equals case. Okay, but I'm still going to draw an edge there. Conceptually, say, oh, we're just done at that point. That's the base case where we have no string left. Cool. And when I said from to 2, actually I meant the reverse. All the edges go from right to left. And then what we're doing is looking for the longest path in this dag. Longest path is maybe a problem we've talked about in problem session, because it's a dag. Well, longest path is the same thing as shortest path. If you just negate all the weights. There are no weights in this picture. So if you just put negative one on all these edges and ask for the shortest path from the base to anywhere, so single source shortest paths from this base, then we would end up getting this path, which, if you look at it, is empty. Empty. And so that shortest path is indeed the right answer. What I've drawn here is the shortest path tree. So also, if you wanted the longest increasing subsequence starting at A, then it is ATY just by following the red arrows here. And how do you get that? You just draw the parent pointers, just like we did before. I didn't mention that. This example can also be solved with shortest paths. Once I construct this graph, you can do the shortest path from some base, I don't know which one to here. If you put negative one on all of the diagonal edges, and you put weight zero everywhere else, then that corresponds to the shortest path in that graph, will correspond to the longest, the path with the most diagonal edges. And that makes sense because the diagonal edges are where we actually get letters in common. And so in this case it's two. So both of these dynamic programs could, instead of writing them as a recursive thing with memoization, or writing them bottom up as a for loop and then doing the computation, you could instead construct a graph and then run DAG shortest paths on it. But the point is, these are the same thing. It's actually a lot simpler to write the dynamic programming code because it's just a for loop and then a recurrence. So you're just updating an array because you already know what the topological order is. You don't have to write a generic depth first search algorithm. Take the finishing order, reverse it and then run this. Run DAG Shortest paths with relaxation. Much simpler to just write down the recurrence once you've figured it out. But they are the same in these examples. In Fibonacci, for example, you cannot write Fibonacci as a single source Shortest paths problem. But a lot of DPs you can write as the shortest paths problem. Just a connection to things we've seen. All right, last example, last problem for today. We'll do more next week. Alternating coin game this is a two player game. We're going to find the optimal strategy in this game. So an example in general you have a sequence of coins. And we have two players. They take turns. So given coins of value v0 to vn minus 1. So it's a sequence, they're given in order, in some order. For example 5, 10, 125, not necessarily sorted order. And the rules of the game are we're going to take turns. I'm going to take turns with U. I'm going to use I and U to refer to the two players. And so in each turn, whoever's turn it is, we get to choose either the first coin or the last coin among the coins that remain. So at the beginning I can choose 5 or 25 and I might think, oh, 25 is really good, that's better than 5, I should choose that. But then of course you're going next and you're going to choose 100 and you'll win the game. You'll get more of the total value of the coins. So in this example, a better strategy is to take the 5 because then the 100 is still in the middle. And so once I take 5, you get to choose 10 or 25. At this point you probably prefer 25 because that's better than 10. But whichever you choose, I can take the 100 and so I get 105 points and you're going to get 35 points. Good example for me. And what we're going to do. So that's easy for a simple example, but in general there are exponentially many strategies here. At each step, either of us could go left or right, choose the leftmost or the rightmost, and we're going to give a dynamic programming algorithm that just solves this fast. I didn't mention. So this algorithm is quadratic time, but it can be made n log n time. It's a fun exercise using a lot of the data structure, augmentation stuff. We've done. You can make this N log N. This algorithm, I think is going to be N squared time. Why? So I won't write the problem exactly, but I think you know the rules choose leftmost or rightmost coin alternating moves. So I'd like to define some subproblems and this is a problem that's very naturally a substring problem. If I just looked at suffixes, that would deal great with if I'm deleting coins from the left, but as soon as I delete and if I delete coins only from the right, that would give me prefixes. But I'll tell you now, there's no dynamic programming where the answer is suffixes and prefixes. You can do suffixes or prefixes, but if you need both, you almost certainly need substrings. Because as soon as I delete the first coin and and then maybe you take the second coin. That's exactly the optimal strategy here. Now you have an arbitrary substring in the middle. But substrings are enough because we're only deleting from the ends, we'll look at substrings. So more precisely, this is just the intuition we're going to define. Some generic X of IJ is going to be. What is the maximum total value I can get from this game if we play it on coins of value VI. To vj? So that's a substring. So this is one way to write down the sub problems and is also a good way, I mean, you can write down a relation. On this definition of sub problems, but I'm low on time. There's two ways to solve this problem. This is a reasonable way exploiting that the game is zero sum. But I'd like to change this a little bit to give you, I think what's a cleaner way to solve the problem, which is to add a third coordinate to my sub problem. So now it's parameterized by three things. P here only has two choices. It's me or U. And this gets at a point that's maybe not totally clear from this definition. Max total value that I can get from this substring of coins. But this is not obviously what I need. So obviously at the beginning I want the whole string and I want to know what my maximum value is. Fine. And I go first. In this game I didn't specify, but I do overloading I. But as soon as I do a move, as soon as I take the first coin, for example, it's now your turn. And so I don't really want to know the maximum total value that I would get if I go first. I'd like to say if player P goes first. I'd really like to know what happens in the case where you go first. And so for some of the substrings, I want to know what happens when you go first. And for some of them, I want to know what happens when I go first. Because as soon as I make a move and it's your turn, and so we're going to flip back and forth between P being me and P being you, P U. So you don't have to parameterize this. There's a way to write the recurrence otherwise. But this is, I think, a lot more intuitive because now we can do a very simple relation which is as follows. So I'm going to split into two cases. One is X of ijme and the other is X of iju. So X of ijme. So I have some substring from I to J. What could I do? I could take the first coin or I could take the second coin. Which should I do? That's my question. What is my first move? Should I take the first coin or the second coin? So this is my question. What is the first move? There are exactly two possible answers to that question. So we can afford to just brute force them and take the max. If we're moving, we want the maximum number of points we can get, maximum total value of the two choices. So if I take from the I side, the left side, that would be X of I plus one J. Sorry. And now crucially, we flip players because then it's your turn. And if I take from the J side, that will make it J minus 1. This is what I accidentally wrote at the beginning of lecture, Also flipped players. So either I shrink on the I side or I shrink on the J side. Oh, I should add on here the value of the coin that I get and add on the value of the coin that I took. So this is an expression inside the max, that sum. And if I take the max of those two options, that is my locally brute forced best choice of what are the total value of coins I will get out of the remainder. Given that you start plus this coin that I took right now in the first step, and for the two possible choices of what that coin is, what remains is how do we define this? X of iju. This is a little bit funnier, but it's conceptually similar. I'm going to write basically the same thing here, but with a me instead of a U, because again, it flips. This is if you go first, then the very next move will be me. Okay, so this is just the symmetric formula here. I can even put the braces in. So far the same. Now I don't put in the plus vi and I don't put in the plus VJ here, because if you're moving, I don't get those points. So there's an asymmetry in this definition. You could define it in different ways, but this is the maximum total value that I would get if you start. So in your first move you get some points, but I don't get any points out of that. So there's no plus vi, there's no plus vj. It's just you either choose the ith coin or you choose the jth coin. And then the coins that remain for me shrink accordingly. Now you're kind of a pain in the ass. You're an adversary. You're trying to minimize my score, potentially, because you're trying to maximize your score. This is a zero sum game, so everything that you get, I don't get. So you want to maximize your score. If you want to maximize your score, you're trying to minimize my score. These are symmetric things. And so if you think for a while the right thing to put here is min. From our perspective, we're imagining what is the worst case that could happen no matter what you do. And we don't have control over what you do. And so we'd really like to see what score would I get if you chose the ith coin, what score do you get if you chose the jth coin? And then what we get is going to be the worst of those two possibilities. So when we get to choose, we're maximizing and this is a general two player phenomenon that when you choose, we end up minimizing because that's the saddest thing that can happen to us. This is one way to write a recurrence relation. We have of course, All of sortbot to do so. The topological order here is in increasing length of substrings. So the T is increasing j minus I start with empty strings. So base case is that x of I me is virtual. So here I'm inclusive in both ends in this definition. So there is a coin I can take at the end, but if you move last and there's one coin left, then I don't get it. So it's zero. Then we have the original problem that is xij me, sorry, x 0n. That's the entire coin set starting with me, that was the problem I wanted to do. And then the running time we get is the number of sub problems. That's theta N squared because we're doing substrings times the amount of non recursive work I do here. That's just a max of two numbers. Very simple constant time. So this is quadratic. Let me show you an example. This is hard to draw, but what I've described here is called solution two in the notes. So here's our sequence. 5, 10, 125 in both directions. And what we're interested in is all substrings. So over here I've written the choice for I. So we start at one of these. And if you start here, you can't end earlier than there. So that's why we're in the upper diagonal of this matrix. And then there's two versions of each problem. The white version and the blue version just down and to the right of it. If you can't, you can't see what blue is. This is the version where you start. This is the version where I start. And I've labeled here all of the different numbers. Please admire because this took a long time to draw. But in particular we have 105 here, meaning that the maximum points I can get are 105. And that's the case because if we look over there, it is the max of these two incoming values plus the VI that I get. So either I go to the left and I take that item or I go down and I take that item. So the option here is I went to the left and took. Well, this is going to be tricky to do in time. The claim is that the best answer here is to go here with 100 and take the five. Because going down corresponds to removing the last item. If I went to the left, that corresponds to removing, sorry, the first item. If I went to the left, that corresponds to removing the last item. So my options are 10 plus 25, which is 35 versus 100 plus 5. 105 wins. So that's why there's a red edge here, showing that was my better choice. And in general, if you follow these parent pointers back, it gives you the optimal strategy in what you should do. First you should take the five is what this is saying because we just clipped off the five we used to start here. Now we start here in this subinterval. Then our opponent to be annoying will take the 25. Doesn't actually matter. I think then we will take the 100. And then they take the 10 and it's game over. All the numbers here, how many points we get. It doesn't say how many points the opponent gets, of course. Of course, you could add that as well. It's just this total sum minus what we get. Now. Let me come back to high level here. What we're really doing is sub problem expansion. And this is an idea that we will expand on next lecture. And the idea is that sometimes you start with the obvious sub problems of prefixes, suffixes or substrings. Here the obvious version was substrings because we're removing from both ends. If you don't know, probably suffixes or prefixes are enough. So we start there. But sometimes that's still not enough sub problems here. As soon as we made a move, our problem almost turned upside down because now it's your turn instead of my turn. And that was just annoying to deal with. And so whenever you run into a new type of problem, just build more sub problems. As long as it stays polynomial number, we'll get polynomial time. And so here we doubled the number of sub problems to just the B case and the U case. And that made this recurrence really easy to write in the notes. You'll see a messier way to write it if you don't do that in the examples we'll see next lecture we're going to do a lot more expansion, maybe multiplying the number of sub problems by N or N squared. And this will give us. It will let us add more constraints to our subproblems like we did in longest increasing subsequence. We added this constraint that we start with a particular item. The more subproblems we have, we can consider more constraints because we'll just brute force all the possible constraints that could apply. Well, we'll see more of that next time. That's it for today.