# 17. Dynamic Programming, Part 3: APSP, Parens, Piano

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=TDo3r5M1LNo
**Transcript page:** https://www.withtranscript.ai/video/TDo3r5M1LNo

## Chapters

- 0:12 — Chapter 1 (0:12)
- 8:44 — Chapter 2 (8:44)
- 14:14 — Chapter 3 (14:14)
- 16:31 — Chapter 4 (16:31)
- 21:25 — Chapter 5 (21:25)
- 25:48 — Chapter 6 (25:48)
- 32:26 — Chapter 7 (32:26)
- 37:34 — Chapter 8 (37:34)
- 44:16 — Chapter 9 (44:16)
- 46:53 — Chapter 10 (46:53)
- 49:42 — Chapter 11 (49:42)
- 52:56 — Chapter 12 (52:56)
- 53:38 — Chapter 13 (53:38)
- 59:28 — Chapter 14 (59:28)
- 1:03:42 — Chapter 15 (63:42)

## Transcript

**[0:12]:** all right welcome back to double o six and our dynamic programming quadruple of lectures we are over halfway through uh into lecture three of four uh today we're going to follow up on this idea of problem constraints and expansion that was mentioned especially towards the end of last lecture we saw an example of sub-problem expansion by a factor of two in the two-player game with coins where we wanted to have two versions of the game one where i go first and one where you go first so this was expanding the number of sub problems by factor of two today we'll see a bunch more examples of this idea including in one setting we've seen already which is bellman ford which you can think of as a dynamic program maybe it's a good time to mention that bellman invented dynamic programming in the 50s same bellman in the bellman ford algorithm this was actually independent discovery

**[1:06]:** by both of them and other people so he invented dynamic programming and then a few years later he applied it to solve the single source shortest paths problem so we saw them in the other order we saw single source shortest paths first because it's a little easier and now we're seeing the general framework that this fits into and so we'll see how how that works uh why did bellman call dynamic programming dynamic programming mostly because it sounded cool and he was trying to impress uh government agencies giving him grants i mean how can you argue with something as cool sounding as dynamic programming but there is some logic to it programming is a reference to an old form of this word which means optimization and generally we're trying to optimize things and instead of optimizing according to some static kind of approach or program we're doing it dynamically this is a reference to the local

**[1:55]:** brute force we're doing to optimize at each stage so you can't tell at the top whether what you're going to do in the middle and so it's kind of each each sub-problem is is behaving differently and so in that sense dynamic it sounds cool all right then we'll go to all pair shortest paths we'll see a new algorithm for that that's not asymptotically any better but it's nice and simple and another way to a cool way to see uh subproblem expansion and then we'll look at a couple of sort of practical problems uh parenthesizing arithmetic expressions and a real world problem piano and guitar fingering so assigning a fingering to how to play a piece and we're going to do that with our sort bot framework so quick recollection of what that is we define subproblems and we saw how to do that for sequences we try either prefixes suffixes or substrings we prefer prefixes

**[2:45]:** and suffix because there's fewer of them if there's more than one sequence we take the product of those spaces um and then the idea we're going to stress today is we can always add sub-problems to make the next step easier in particular adding constraints to sub-problems in some sense lets us remember things about the subproblem that's calling us or about the past is one way to think about it or in general to remember state just by adding more sub problems we can remember more stuff not just what things we're working on but some context and that's what we'll see lots of examples of today it'll hopefully make sense by the end of the lecture then we need to relate these sub problems with a recurrence relation which we usually just call a relation and the key idea here is to come up with a question that if you knew the answer to that question you

**[3:36]:** could reduce the subproblem you're trying to solve to smaller sub-problem solutions so this question is sort of the fundamental aspect of some fundamental aspect of a solution typically when you're dealing with suffixes you want to ask some question about the first item s of i when you're dealing with prefixes you want to ask a question about some the near the last item s of i minus one and for sub strings who knows somewhere in the middle we'll see an example of that today once you have this is a reveal late something coming later uh once you have identified such a question the dynamic programming approach is don't be smart about how to answer that question just locally brute force try all possible answers to the question for each one recurse and take the best solution according to whatever metric you're trying to do typically minimization or maximization another way to think of this local bird

**[4:35]:** force which i like to think in my head so maybe some people like this some people don't is to think about guessing the answer to the question and so you know maybe the the answer could be zero one or two and uh my algorithm will say guess which is the right answer and i'll assume that my algorithm correctly guesses the answer and analyze that so we can think of the program as going straight through uh you know guessing the answer and then recursing and then combining the solutions however but then at the end of course we can't assume that the guess was correct in fact we have to loop over all those guesses so it's the same thing just if you think of it this way there's less looping in your program but when you analyze it definitely the loop is really there you have to pay for all the possible answers okay uh then

**[5:23]:** we need to make sure this relation is acyclic get a subproblem dag and i like to specify an explicit topological order to make that clear we have base cases for the relation we have to solve the original problem in terms of these sub problems and then we analyze the running time usually as the number of sub-problems times the non-recursive work in each in the relation so recursion is free because we're multiplying by the number of subproblems you can also sum over the sub-problems sometimes that gives you a tighter bound and then of course we also have to add on the running time we spend in the original problem all right so that was quick recap now one problem we saw in this framework uh two lectures ago the first lecture was single source shortest paths in a dag which a lot of dynamic programs actually can be reduced to shorter single short shortest paths on

**[6:12]:** a dag in fact the reverse is true single source shortest paths and a dag can be thought of the dag relaxation algorithm we saw is essentially a dynamic program where the sub problems are delta of sv the relation is delta of sv is the min so what are we thinking about here we're guessing this is sort of a new uh phrase i want to add we're guessing uh oh actually i wrote it right here the last edge uv on a shortest s to v path right so delta of sv the problem we're trying to solve is uh find shortest s to v path and it's you know it's some path and we don't know what it looks like but uh some feature of the solution of this path we're trying to find is well what's the last edge it comes from some vertex u unless the path is of length 0 and you know s

**[7:02]:** equals v that's a special case dealt with in the base case otherwise there's some vertex u before v we don't know what it is so we're going to locally brute force or guess what the right answer is so look at all incoming edges from u to v and for each of them take the recursive shortest path from s to u plus the weight of the edge okay so this is the guessing or local brute force perspective and the reason this works is because g is acyclic and so it has a topological order otherwise if graph if the graph has a cycle and that's the case we want to go to next uh this recursive call from delta of sv to delta of su will have loops in it and so you'll never evaluate this recursion you'll never finish you'll never memoize you'll be sad it'll take infinite time alright so don't use this algorithm unless

**[7:49]:** you have a dag for dag it's great it's linear time so that was a little review now here is a single source shortest paths in general graphs which we know as bellman ford but rephrased into the sort bot framework okay so uh we defined this problem in the bellman ford lecture delta sub k of sv remember this was the weight of the shortest path from s to v that is restricted to use at most k edges this made the problem feasible we ended up taking the product of the graph into many into you know all these different subproblems in fact but from the perspective of dynamic programming we think of this as a subproblem constraint what we really want is the shortest suv path but that's hard so we're going to break it up into smaller pieces for each k between zero and v we're going to say well let's think about this problem restricted

**[8:44]:** to use at most k edges and we and for simple paths you know if there are no negative weight cycles we only have to go up to v minus one uh we prove that and we know then we're happy but that's that's sort of the last thing we want to solve so if we look down at the original problem we want it's delta sub v minus 1 of sv for all v so though if we could solve these sub problems as we saw with bowman ford we can solve the original problem unless there are negative weight cycles and we use delta sub v of sv to check whether they're negative weight cycles i don't want to repeat that but that's the all in the original problem and then we can take this relation that we wrote for dag shortest paths and just port it over here so remember this for a general graph this has

**[9:30]:** cycles so we can't use it because we're just referring to arbitrary delta of svs so there's no reason to expect no cycles there in fact the call graph is exactly the graph g so it has a cycle if only if g does but now over here i'm writing exactly the same formula for this min but i added a sub k here and a sub k minus 1 here the observation being if i've already guessed what the last edge uv is for this path then if this whole thing has length at most k then this piece has length at most k minus 1. so i only need to do solve delta sub k minus 1 of sv here and so that's what i wrote sorry i have s u that's what i wrote here there's one other thing which is as i mentioned a little while ago it could be that we use fewer than k edges and so let's consider the case where we don't follow a last edge and we just add to this min the uh shortest path using at

**[10:37]:** most k minus one edges that's one option for having at most k edges if we wrote equality here then we would remove that like the last problem session okay good so the key observation here is that this recurrence does not have cycles just by adding this index if we solve these problems in order of increasing k all of the references from delta sub k are in terms of delta sub k minus 1 and so this is now magically acyclic this is why bellman ford worked this but now i think in a very pleasing way we're taking our graph that cyclic and by spreading it out over various copies of k and referencing always the smaller one we get an acyclic graph acyclic relations we have base cases like normal and then we can analyze the running time in the usual way which is uh summing so uh what is this uh how much does this

**[11:35]:** cost we're going to take this the cost of computing the relation which is the number of incoming edges to v that's this theta and then some overall sub problems so sum over k and sum over v i wrote it as a sum instead of our product because this thing is theta e right the sum of incoming edges over all vertices is exactly the size of e and then we sum there's no k in this formula so we just multiply by v and we get v e so our good friend belmont ford recast kind of the opposite way before we were using relaxations now we're just writing them in explicitly but essentially the same computation just in a different order okay cool so those are reviews of old algorithms but in this new framework show how powerful it is let's look at another example which is our friend right here all pairs shortest paths okay a

**[12:40]:** few lectures ago we saw johnson's algorithm which solves this very well so one option we could use is just this same set of sub problems but for all u and v right so for u and v and v that's what we really care about um and then we could say k up to v something like that so this would work but it would give the same running time as running bellman ford v times this is one solution we know but not the best solution we know for how to solve shortest paths so this would give v squared e which is at most v to the fourth for dense graphs it is theta v to the fourth so this is v times v times e um but worst case is v to the fourth uh what i'd like to show you now is a different way to solve this problem almost identical but gives v cubed

**[13:39]:** running time which for dense graphs is really good so we're going to reduce this 4 down to a 3. this is an algorithm called floyd warshall it's definitely not an obvious algorithm it's a very cool idea and it's a nice example of a different way remember this is sub problem expansion we took the problems we cared about multiplied by this choice of k here we're going to do the same thing but define it differently we're going to define those sub problems differently so first i want to number the vertices

**[14:14]:** starting at 1 for convenience so let's see why and then we're going to define some sub problems which are delta i'll call it u v comma k maybe to avoid conflict i will write a d here this is just a definition local to this algorithm so i want the weight of shortest s to v path

**[14:51]:** okay so far just the same as the problem we actually want to solve this is delta of sorry uv but i'm going to add a constraint which is using only vertices in uv and 1 2 up to k so this is the divine inspiration to define sub problems this way it's a different constraint than the one we saw here which was using at most k edges so in some sense what's slow about this algorithm is that we have to loop over all the incoming vertices this is expensive you know costs order the degree which ends up with an e term we're going to try to convert that e term into a v term by just knowing which vertex to come from which sounds impossible but it turns out if you write the sub problems this way so i'm naming the vertices and say well let me just find a path that uses uv and the vertex labeled one there's only like two options i could go straight from u to v or i could go

**[16:07]:** from u to one to v and then how about with one and two and one and two and three the same vertices okay by label instead of by counting them slight tweak but it turns out this uh speeds up the algorithm so let me first tell you how many sub problems there are

**[16:31]:** okay this is uh v cubed sub problems two choices for u and v and i have uh v choices for sorry i have v choices for u v choices for v and v choices for k roughly v cubed of these uh but the key thing is that sounds like a lot but the relation becomes cheaper now because i can just write delta u sorry d of uvk is the min of two things d of u v k minus one and d of u k k minus one plus d of k v k minus one okay it's a strange it's a strange formula because we're using indices like k for vertices also um as well as u and v for vertices but we're also using k as a counter but we can do this because our vertices are numbered okay so the idea is the following we have vertex u we have a vertex v and

**[17:44]:** we've already found the shortest path that uses vertices 1 through k minus 1 that's what this quantity is so it could be and now we're thinking we're trying to add in this vertex k and think about what are all the paths that could go from u to v using one up to k well it could be the shortest path from u to v using one up to k doesn't use vertex k that's the first option just use vertices one up to k minus one maybe we don't need to use k or it could be that the path goes through k well it starts at u and it goes to k and then it goes from k to v okay all using for simple paths if we assume there are no negative weight cycles and you have to run down and forward to detect them but assuming no negative weight cycles the shortest path from u

**[18:29]:** to v through k must start by using vertices less than k and then use vertices less than k again and that's what i've written here it's from u to k using k minus 1 up to k minus 1 labels and from k to v using labels up to k minus one okay the cool thing here is the min only has two terms so this takes constant time non-recursive work so this is uh k is not on the shortest path and this is k is on the shortest path

**[19:02]:** cool so this is constant non-recursive work so if we jump ahead to the running time with this algorithm we get the number of sub-problems which is v cubed times the number the amount of work per sub-problem which is constant so that's just a v cubed algorithm for dense graphs this is really good this is when e is v squared then this is the same thing as v times e so as good as bellman ford uh it's not as good as johnson for sparse graphs sparse graphs remember or in general with with johnson we got v squared log n plus v e and this is always spending v cubed but it's cool because it's a very simple algorithm let's uh quickly write the topological order this is all we need is to guarantee that we solve problems in increasing k order because every reference here is to a smaller k for the third argument um and

**[20:16]:** so for example you can just write a tripoli nested loop k equals zero one up to v and um u and v and v and v so if you wanted to write this algorithm bottom up you just write this triple for loop and then plug in this recurrence relation here and think of d as a table as a set mapping instead of uh as a function call and boom in four lines you've got your algorithm except you also need a base case base case here is uv0 so i have to define what that means but when k equals zero the one through k set is empty so all i'm allowed to use are use my vertices u and v and so there are three cases for this 0 if u equals v it's w of uv if there's an edge from u to v and it's infinity otherwise

**[21:25]:** okay but easy base case constant time for each and then the original problems we want to solve are delta u v sides of v because i number the vertices one through size of v and if k equals size of v that means i get to use all my vertices so that is regular shortest paths this is assuming no negative weight cycles okay we already know how to do negative weight cycle detection so i'm not going to talk about that again but then this will be my shortest pathways because uh yeah i implicitly assumed here that my path was simple because i imagine that i only use k once zero or one time and that's true if there are no negative weight cycles cool and we already did the time part of sort bot so v cubed algorithm very simple basically five lines of code and you've got all pair shortest paths and if your graph

**[22:26]:** is dense this is a great running time if your grass graph is not dense you should use johnson like you will and or like you have implemented in your problem set yeah so how was this compared to just running dijkstra's outdoor a bunch of times ah what about using dijkstra so let's compute so uh running dijkstra v times is the running time of um

**[22:52]:** johnson so running dijkstra a bunch of times is great if your graph has only non-negative edge weights then you should just run dijkstra you get this running time and for sparse graphs this is superior if you have negative edge weights you should run johnson which is bellman ford once and then dijkstra v times and we're comparing this to the cubed which we just got so this i mean how these compare depends on how v and e relate so on the one hand maybe uh v is theta e that's what i would call a very sparse graph it's quite common then the running time we get here is uh v squared log v okay roughly v squared on the other hand if we have a very dense graph v is theta e squared which for simple graphs the most we could hope for uh then this running time is v cubed okay so if you know the

**[24:01]:** v is near e squared then this is giving you v cubed anyway from the ve term so why not just use this algorithm and often you know a priori whether your graph is very sparse or very dense or somewhere in between if it's somewhere in between you should still use johnson's algorithm because you're going to get the benefit from sparsity and only have to pay this ve instead of the v cubed but if you know ahead of time you know constant fraction of the edges are there then just use uh or you have a small enough graph that you don't care just run a floyd washall because it's simple and fast good question any other questions so this is an example of sub problem expansion a very non-intuitive one where we use some prefix of the vertices but notice it's prefixes again right i numbered the vertices from 1 up to v and i took

**[24:49]:** a prefix of those vertices so i just solved the problem using prefix vertices 1 through k so it's actually a familiar idea if if all you'd seen are all our dynamic programming examples of prefixes suffixes substrings actually it's a pretty natural way to solve for his paths maybe even more natural than this anyway all right enough shortest paths let's solve two more problems that are more in our standard wheelhouse they will involve sequences of inputs not graphs first one is arithmetic parenthesization so first let me define this problem

**[25:48]:** okay we are given a formula with say plus and times let me give you an actual example seven plus four times three plus five okay now when you read this because you've been well trained you think okay i'm going to multiply 4 and 3 first because that has a higher precedence and then i'll add the results up but uh what i'm going to let you do is parenthesize this expression however you want for example you can add parentheses here and here okay you must make a balanced parenthesis expression a valid way to to pair up or not just para but a valid way to evaluate this expression any ordering you want uh i could be inconsistent i could for example do this sum and then do this product and then do this sum okay but some kind of expression tree uh over this and each one evaluates to something so this is 11 and this

**[26:50]:** is eight and so this is 88 and my goal is to maximize that computation and i claim that this is the way to maximize that particular example okay so let me write it in general and get my notation to match notes so given a formula

**[27:16]:** a0 star 1 a1 star 2 a2 and so on up to star n minus 1 a n minus 1

**[27:32]:** where each a i is an integer as we like in this class and each star i is either plus or times okay so i'm using star as a generic operator it's it has chose star because it is the superposition of star on time on top of a time symbol so it's clear so you're given some formula any mixture of plus and times that you like involving n integers and your goal is to place parentheses to maximize the result okay so you can try all the combinations here if i for example take the product of 4 times 3 i get 12. for if i do that first i get 12. then if i add 5 and 7 i get 24 which is less than 88. and i checked them all and this one is the maximum for that example okay so interesting problem um sort of it's a bit of a toy problem but it's motivated by lots of actual problems which i won't go

**[28:46]:** into here so to apply this framework you know we need to identify some sub-problems this is a sequence problem we're given a sequence of symbols and so natural things to try our prefixes suffixes and substrings i'm going to jump ahead and think about the relation first i want to identify some question about the sub-problem or its solution that would let me reduce to smaller sub problems this is a little trickier this is very different we're not always doing something on the left or on the right or we can't assume there's something happening on the left because maybe we take a product in the middle first if i take a product in the middle first then i have some result here but i still have three things i have the thing to the left i have the thing in the middle and i have the thing on the right it turns out to be very messy

**[29:33]:** to think about what the first operation is because we can think of this as a tree um where we take a product here we take a sum of 7 and 4 and 3 and 5 over here and then take the product at the root but i don't know what the tree is right i only know these numbers and these operators but i don't know how to organize this tree and so the idea is if you think of this tree what is the one thing that's the easiest to identify it's the root the root corresponds to the last operation i do in this computation the last thing i did was take a product and that's a lot easier because uh if i guess who's at the root which operator is at the root that naturally decomposes into the left subtree and the right subtree and those will always

**[30:23]:** be substrings we kind of know this this node corresponds to everything left of this operator and this sub substring or this subtree corresponds to everything to the right of the operator so this is our idea is we're going to guess

**[30:48]:** which operation star i is evaluated last

**[30:59]:** or in other words at the root so this is a question it has uh n possible answers i guess actually n minus one from operator one to operator n minus one and so uh we'll just brute force all those choices okay so i wanted to start here because uh to realize that if i choose some star i in the middle which might be the right thing like in this example star i is the the middle one middle operator i naturally decompose into everything to the left of that operator and everything to the right of that operator this is a prefix this is a suffix so you might think oh my sub problems are all prefixes and all suffixes but that would be wrong because if you have a bunch of operators and say you choose this one to be last so i have a prefix here and a suffix here and then there'll be some

**[31:58]:** within this suffix i'll choose some operator to be the root of that one and i have a prefix and a suffix of this suffix but in particular i will have to evaluate this sub-problem which is a prefix of a suffix in other words a substring so never use a mixture of prefixes and suffixes if you need both you probably need all sub strings so our sub

**[32:26]:** problems are going to be substrings

**[32:36]:** okay i'm not going to write the sub problems quite yet because there's another idea we need so what do i need to do with a substring so i'm going to guess the middle operator and then evaluate the left substring evaluate the right substring what am i trying to do with those substrings i guess i'm trying to solve this problem which is place parentheses in order to maximize the result and then return what the result is okay and i can use parent pointers to reconstruct what the parentheses actually are so is it enough once i guess what the last operator is is it enough to maximize the part to the right and maximize the part to the left will that always maximize my sum or product according to what this operator is and you think about it for a while yeah if i want to maximize a sum i should maximize the two parts and if i want to maximize a product i should maximize the two parts that

**[33:31]:** seems right except i didn't say that my integers are positive so it's true if the integers are positive but to make this problem more interesting we're going to allow the integers to be negative so for example uh 7 plus minus 4 times 3 plus minus 5. so i just added a couple of minuses to a couple of the numbers here then it's no longer best to pair them this way so if i pair them this way like this or if i add parentheses this way i get 3 here and i get minus 2 here so i get product of that as negative 6 which is probably not the maximum in fact i can do better i believe by doing the left operator last

**[34:28]:** so this is a i claim the best parenthesization if i remembered it correctly so this is minus two times minus four is eight uh plus seven is fifteen okay so i got a positive number definitely better than the negative number i got and i claim this is the best and the key property here is when we take a product of two negative numbers we get a positive number so sometimes you actually want to make things small because small might mean very negative you take two very big negative numbers very small negative numbers in other words you take their product you get a very big product positively because the signs cancel okay so this seems tricky we want to work on substrings but we don't know whether we're trying to maximize or you might think well maybe i'm trying to maximize the absolute value but that's not good maybe overall on this entire expression i get

**[35:22]:** negative a million and that's not what i wanted i wanted to maximize the sum so i need to i still need to solve the max uh evaluation that i can get the max parenthesization but i also need to solve the min parenthesization if i can solve max and min i'll know the entire kind of range that i could get and i really only i'll care about men especially when it lets me go negative but let's just solve it in all cases the min and the max and then just brute force the rest that's what i'm going to write down so that was some motivation on why we are going to define subproblems this way so i'm going to define x of i comma j comma opt to be so opt here is going to be either min or max and this is my sub problem expansion i really just care about max at the very

**[36:18]:** end but i'm going to care about min along the way and i j is going to specify my substring so this is going to be the opt value opt stands for optimum here or optimization uh the upped value i can get for the substring a i start plus one a i plus one and so on to uh star j minus one a j minus one okay being careful to get my indices correct here and i want uh 0 less than or equal to i less than j less than or equal to n i claim and opt like this okay so i'm going to get the mean value and the max value separately those are two different sub problems it's my expansion this is the constraint i'm adding and i'm only focusing on this substring from i inclusive to j exclusive okay so i claim those are good sub problems let's write down a recurrence

**[37:34]:** relation

**[37:48]:** okay

**[37:55]:** so i want to write x of i j off on the left and i want to optimize so this will be min or max on a set of choices what is my set of choices well uh like i said i want to guess what is the last operation evaluated i wrote star i here but star i is already defined so i'm going to use star k so i'm going to guess what which of my operations between i plus 1 and j minus 1 is the last one and i evaluate and that decomposes into everything left of k so that would be x of i uh comma k comma something and then we will do operator star k on the part after k which is from k to j something okay and i'm choosing between i think it's i less than k less than j so k is some operator in between because i started i

**[39:04]:** plus 1 and i end at j minus 1 so those are the possible choices for k i tried them all that's my local brute force and then i take what i can get on the left what i can get on the right and multiply or add them according to whether that operator is plus or times now should i maximize or minimize this one should i maximize or minimize this one i don't know so i'm just gonna do more local brute force um i'll say well let's just say opt prime for the left or maybe i'll call it opt l for left and opt r for the right part and i'll just add this to my for loop let's just try uh opt l and opt r just take all possible choices among min and max

**[39:55]:** you know you could think hard and for addition for example if you're maximizing you should really only need to maximize the two parts and if you're minimizing you you can prove you only need to minimize the two parts but let's for multiplication it's messy it could be really any of the options because sometimes when you minimize you get a negative term sometimes when you sometimes you don't and so you know it depends what you're trying to do you have to consider all the signs but we don't need to think hard we can just try all options there's only four choices for opt l and opt r among min and max you could do mid min min max max min and max max so try it's just a multiplication by four in this for loop the big cost is actually this one because there are j minus i choices for k there's a constant number of

**[40:44]:** choices for opt l and opt r and you need to prove that this is correct i won't do it here but the idea is if you're trying to minimize or maximize your sum or product it's enough to know what ranges these could come in the optimal choice will always be an extreme in that range okay and that's we consider all of them here and so we get this recurrence now it needs a base case and we need to check that it's acyclic but topological order is just increasing j minus i this is the usual order for um for substring problems because this is increasing length of the substring so start with very tiny substrings here we'll start with length one substrings we just have an ai there so that's going to be our base case and you grow up to the entire string and it doesn't matter how we order relative to opt as long

**[41:39]:** as we are increasing in j minus i because i decay and k to j will always be strictly smaller than i to j and so this will be acyclic the base case is x of i i plus 1 opt this is always a i doesn't matter what opt is because there's nothing there's no choice you just have a single number in that substring because we're exclusive on i plus 1. okay and then the original problem we want to solve is x of 0 n max could also solve min and see how small you can get it so if you wanted to maximize the absolute value you could solve the max problem and the min problem and take the largest of those two options and how much time does this take well how many sub problems are there for substring problems we have n squared sub problems now we

**[42:32]:** multiplied the number of subproblems by 2 but that's still n squared okay so we have n squared sub problems

**[42:42]:** and how much work per subproblem are we doing well uh as i mentioned we're we're doing j minus i choices for k constant number of choices for opt l and opt r so this is theta j minus i which if i'll be sloppy that's at most big o of n and it turns out to be the right answer anyway so uh there's linear amount of non-recursive work in fact it's like a triangular number but uh that's still theta uh n cubed

**[43:14]:** okay same running time as uh v cubed we just got but polynomial time and this is pretty impressive because we're really brute forcing all possible parenthesizations they're about four to the n exponentially many uh parenthesizations of an expression but we're finding the biggest the one that evaluates to the largest value and the one that evaluates the smallest value in just n cubed time polynomial and a key here was subproblem expansion where we in addition to solving the max problem we also solved the min problem because sometimes you want to take two very small negative numbers and product them together to get a larger positive number cool question would anything go wrong if i added minus a divide so what if i had operators minus and divide uh it's a good question i'm i'm certain that minus should work fine if we do min and max

**[44:16]:** this will still evaluate the should still evaluate the largest thing for division i need to think about the cases i would guess it works but what we need to prove is that the way to maximize or minimize a division say given two numbers in the left and right uh is that it either corresponds to maximizing or minimizing the thing on the left and then maximize or minimizing the thing on the right so as long as you have this kind of it's not exactly monotonicity it's just that in order to compute max or min it suffices to know the maximum of the two parts it's like interval arithmetic you know interval arithmetic i want to know what is the what are the extremes i can get on the output of a division if i'm given that a number is in some interval here and some interval here if the answer is always use one of the

**[45:06]:** extreme endpoints here and use one of the extreme endpoints here then this algorithm will work otherwise all bets are off cool so if you negate if you put a minus here that will work fine because it's just negating this range and then it's just like sum but oh divided be careful about zero yeah actually so it doesn't work because we care about how close this can get to zero for division it might be enough to to consider those it's like instead of minimizing and instead of computing this entire interval if this interval spans 0 maybe i need to know if zero is here i need to know how close to zero i can get on the left side and how close to zero i can get on the right side still just four quantities i need to know i would guess for division that's enough yeah nice solid little problem so then we'd be multiplying

**[45:58]:** the sub problem space instead of by two by four hey maybe we should put this on the final no now it's in lecture so we can't use it but it's a cool it's a cool set of problems right you can do a lot with dynamic programming just uh you don't need to be that clever just brute force anything that seems hard and when it works it works great all right and this class is all about understanding when it works and when it doesn't work of course we will only give you problems where it works but it's important to understand when it doesn't work for example dag shortest paths that algorithm on a non-dag very bad infinite time okay our last example is piano fingering

**[46:53]:** so here we're given a sequence of notes

**[47:02]:** t zero t one t for note up to n t n minus one um these are single notes and all the single notes all the single notes right and we have fingers on our hands this is not like two-finger algorithm this is the five-finger algorithm uh so in general i'm going to assume an arbitrary uh anthropomorphic object so this is five for humans most humans some humans i think the maximum on each hand is seven could be smaller maybe you've had an accident okay i'll solve it for arbitrary f and what we'd like to do is assign fingers to notes to tell our pianist which finger to use for each note so normally when you're given sheet music it just gives you a sequence of notes you want to play it doesn't tell you which finger you want to play it with unless you have some nice uh training booklets and they have a little number on top of each and then you number them one two three four five and symmetrically one two

**[48:17]:** three four five and so here's a giant piano for my giant hands um so uh if jason were here he could sing these notes so maybe i play this with my first finger this with my second finger let's just say i'm doing a scale so i can walk and now i think typical way to do a scale is to reach over with your first finger second finger i guess and then do something like this no okay clearly i don't know scales um or how to play a piano but you know there's there's limits here i can if i'm going from this note and i want to go to another note uh over here okay maybe i have a decent span from first finger to fifth finger but my span from my first finger to my second finger is not as big i can't reach as far so if i want to play this note and

**[49:02]:** then this note i'd like to start here with a very extreme finger on the left and then go to a very extreme finger on the right so i'm going to formalize this problem pretty abstractly because i don't want to get into music performance i'm going to say that there's a metric d for if i'm at note t with finger f and i want to go to note t prime with finger f prime then this function d of t f t prime f prime gives me the difficulty of doing that

**[49:42]:** the difficulty of playing note t with finger f and then playing note t prime with finger f prime it's w is width uh so this is a transition difficulty i'm not going to worry about difficulty of the whole piece other than saying i've got to play this note then i've got to play this note and for now just single notes you play a single note with your right hand then you play another single note with your right hand then another single note with your right hand let's assume no pauses for now no rests and great so we uh have this difficulty from going from the ith note to the i plus first note and then our goal is to minimize the sum of difficulties minimum sum of d t i f i t i plus 1 f i plus 1. and these f i's and f i plus 1 is what we want to compute we don't know which fingers to use we're only given which notes to play okay so this is actually a natural problem there are lots

**[50:55]:** of papers about this problem i've read a bunch of them obviously not super well about how to compute how to play scales but um there are notes like are there there are constraints in this usually people write this metric as a sum of different penalty terms if i want to minimize difficulty difficulty is high if i play a note far on the left on the left so if i go from a low note to a high note that's easier to do if i use a lower numbered finger and go to a higher numbered finger you don't want the you don't want to go like i was doing from a high numbered finger to a low numbered finger to play a note on the right that's annoying so i'd like to do an assignment if i can that avoids that so i'll just have some penalty of like 100 if that happens and zero if it

**[51:43]:** doesn't happen sum up a bunch of terms like that other examples are avoid the fourth and fifth fingers the weak fingers or if i'm playing a portion of the song that is legato then i don't want to use the same finger to play two notes uh right after the other i've gotta use two different fingers for that so you have a penalty if f i equals f i plus one and these two notes are not the same uh then and we're in legato mode then we add a penalty term and things like that i would prefer if i'm going from a very low note to a very high note i'd like to use more extreme fingers things like that okay but we're just going to assume this di d function is given to us it's some you know const was some polynomial size if you imagine the notes on your keyboard are n notes or

**[52:34]:** m notes then some polynomial and m size to this function okay so how do we solve this problem i'm running low on time so let me give you

**[52:56]:** the idea and this is going to use sub-problem expansion

**[53:06]:** so the sub-problems are going to be x of i comma f this is the minimum total difficulty to play a suffix because i like suffixes ti up to tn minus one uh starting

**[53:32]:** with finger f

**[53:38]:** uh on note ti okay so the obvious sub problems would be without this constraint this here is a sub problem constraint and you could try to define the sub problems just as what's the best way to play a suffix but i claim it's important to know which finger we start with so we're going to multiply the number of sub-problems by capital f which is just five so very small sub-problem expansion and then we're going to constrain each sub-problem to say well what if i started with my first finger what if i started with my second finger what if up to the fifth finger try them all okay then i turns out i can write a relation which is x of i f equals the min what should i what should i min over i'll just uh guess this i'm already told what my first finger is to use which finger i should use for ti

**[54:35]:** so what's the next thing that matters well i guess what finger to use for the ti plus one the very next note which what is the next finger i use i will call that f prime and minimize over f prime between one and capital f of the remaining suffix starting with f prime plus my difficulty function from t i comma f to t i plus 1 comma f prime end of bracket okay so there's kind of a lot going here this is a lowercase f prime but actually if you think about what i'd like to write the recurrence on i start with the suffix i i like to recurse on the smaller suffix so that's x of i plus one and so here uh if if i know that i'm parametrizing by finger number for i well then i in order to even call this function i need to know what finger i'm using for

**[55:35]:** i plus one so once you decide on these sub problems it's really obvious you need to guess what is the next finger and then recurse on that finger recurs on the remaining suffix of that finger now why did we need to know what f what these fingers were why not just guess what the first finger is uh well it has to do with this difficulty function for this difficulty function i know that i want to measure the difficulty from t i to t i plus one and to do that because this function is parametrized by four things i need to know both the finger for ti and at the same time the finger for ti plus one if i remove this f i could you know add a min over one finger but i can't really add a min over two fingers so what this does by parameterizing by f here and writing down the

**[56:21]:** optimal for each starting finger f i can at some sense i'm remembering in this call what finger i started with because i told it you have to start with finger f prime and so locally to x i f um i know what finger f prime is being used for t i plus pos1 and also because of the definition of x i f i know what finger i'm using for ti and so i get to know both of these fingers one comes out of this min and the other is given to me as this parameter and then of course if i can solve these problems i can solve the original problem by just one more min of 1 up 1 up to capital f of x 0 little f right i don't know which finger to start with but that's just f choices and so then this recurrence gives me the overall solution in i'll just

**[57:19]:** jump to the time you need a base case and uh topological order but it is n f squared time there are n times f sub problems here and for each one i'm doing an optimization over f choices so i get n times f squared it's a polynomial and if f is a constant this is actually linear time very fast dp now what i described here is for one hand one note at a time but you can generalize this to two hands each with one note well that's just ten fingers so uh you could solve this separately for the right hand and left hand if you know which notes are being played with left-handed right hand but some pieces that's not obvious so to make it more interesting what if you have multiple notes at the same time and let's say i think it's reasonable so you can only play up to f notes at a

**[58:09]:** time one for each finger and so we have an upper bound of the number of notes at a time that we're playing which is good oh i have a drawing of this dp by the way as a subproblem dag so this is the original problem which is we don't know which finger to start with but then we just have a complete bipartite graph here where we write on each of these edges what is the difficulty of this transition the y axis here is which finger i'm using one two three four five and the x-axis is which suffix i'm considering which note do i start on and so you could solve this with shortest paths and a dag or you could just solve it directly this dp either top down or bottom up okay jumping ahead so if you do multiple notes at a time instead of this finger choice which just had f choices we

**[59:04]:** have

**[59:08]:** what do i write here t to the f uh possible states where t is the maximum number of notes that i could play at once

**[59:28]:** and usually this is at most f one for finger but we could generalize and this is you know number of fingers so i could deal with all 10 fingers of a typical human set of arms hands and say there's at most 10 and so this is 10 to the 10. it's a big constant but it's constant uh like a billion billion right 10 billion but then is that times n and maybe that squared times n will let me exhaustively enumerate all the possible things i could do be doing with all of my hands so you can apply this not only to piano fingering but also to guitar fingering also to rock band rock band is an easy case where you just have five buttons and usually only four fingers that you use and this doesn't really make any sound so it's not that exciting so the case where f equals four is uh you can apply to optimally figure out which which finger once you have a

**[1:00:28]:** difficulty function of what transitions are easy and hard for rock band then you can optimally figure out your fingering for rock band songs with a real guitar this is a little bit harder and because there are actually multiple ways to play the same note for example i can play the note of this string like this these should both sound the same my guitar were perfectly tuned which is not and that's you know properties of strings and the way these things are are played so in addition to what finger i use i should also decide which string to play that note on if all i'm given is sheet music different notes to play another thing i could guess is which string to play that note on so for example maybe i want to play my favorite song here

**[1:01:26]:** the super mario brothers my favorite song um i can keep going but i actually can't keep going it won't be as impressive uh i don't actually know how to play guitar uh but the there are a lot of choices there right um i started with uh playing this note down on this um down on this string that's good i could have also played it on this string but that's more work for my finger so i have a diff penalty function that says well if i play an open string that's a lot easier and then i had a transition from here this note to this note to this note and if you focus on my fingering here i chose to use my index finger for the first one because that index finger is always the easiest to use but also gives me lots of room to move my pinky over to here and then i like

**[1:02:15]:** to use my middle finger to come up here you could also use your index finger it's just a little bit more of a reach so you have to define some difficulty function it might depend on how big your fingers are you can do that and then optimize using these algorithms what is the best guitar fingering for a given piece one note at a time or several notes at a time you could even add in parameters like oh maybe i want to play a bar that's not a perfect bar but this would be great for my playing this note down here and this note up here bad example uh so you could do other things with the guitar to make it more interesting and you know generalize this dynamic program suitably but i think this gives you a flavor how with subproblem expansion i can capture almost any aspect of a problem that i want as

**[1:03:06]:** long as the number of states that i need to keep track of is small i can just multiply the number of subproblems by that state and i can keep track of any kind of transition from one state to another which i could also do with taking the product of a graph but dynamic programming gives you a kind of methodical way to think about this by figuring out some property in this case the state of how my how my fingers are applied to the instrument and then just sort of brute forcing the rest a very powerful

**[1:03:42]:** framework you
