The big idea behind Interval DP (Dynamic Programming)

Added: 2026-05-16

[00:00:00]I recently uploaded a video on my YouTube channel that talked about three different approaches to solve the problem of counting the number of distinct subsequences using DP. In that video, I got an interesting comment that talked about why the difficult part of dynamic programming is coming up with the DP definition or the DP state. And once you have the DP definition with you and you are convinced that your DP definition is correct, you will eventually be able to find out the transitions. While I do agree with the sentiments of this comment, in this video I want to show you both sides of the coin. That is we will first look at a problem where the DP definition is very simple and easy to come up with but the transitions are almost impossible to notice if you are not experienced in this field. And it we will also look at the flip side of the coin where the DP definition is almost impossible to come up with if you have not solved a lot of DP problems beforehand. But once I tell you the DP definitions, the transitions become trivial. So we'll look at both the problems in this video. Now I want to clarify that the goal of this video is not to help you gain more intuition about DP problem or to show you how there are a lot of sub problem and why we should use DP. Instead the goal of this video is to show you some various DP patterns that exist in terms of transitions as well as states especially for interval DP. So that even if you aren't able to come up with the parameters and the transitions by yourself, but if you solve these two problems, then you will have unlocked a new paradigm of DP that you can possibly try out in future problems because sure you might spend 1 day, 2 day, 10 days or even 1 month to figure out the correct DP parameters and transition and you will eventually be able to solve this problem. No doubt about it. But I want to speed things up.

[00:02:12]That is let's leave all that behind and let me convince you that this is the DP definition. Now your goal is to find out the transitions. And in the other problem I will try to uh ask you what is the DP definition and then we can see how to uh get the transitions. So let's discuss the problem statement. So one of these problem is from lead code and one of them is from code forces. Now do let me know in the comment section which one do you think is from code forces and which one do you think is from lead code and what is the estimated difficulty of this problem as per you.

[00:02:53]So the problem statement let's start with the easy version first. So it says that you are given a string and in one operation you can delete identical characters of a string if they are part of the same substring. So you can see that in one operation you can delete d and d and after deletion gaps would be created over here and this gaps would be filled by the elements concatenating. So the strings becomes a b c ba then you can delete another set of identical characters. So you can see you can delete C and C and it would become A B A. Then once you delete B and B it will become A and A. Then you can delete them together and you will get the empty string. So you can see that you took four operations to delete the entire string. So your goal is to find out given a string how many number of minimum number of moves that you have to do such that the final string is empty.

[00:03:52]This is the easy version of the problem and then later in the video we'll discuss also a hard version of the problem which says that if you want to delete this D and D then the length is two so the cost would be four. But if it had been D and D then the length is three and the cost would have been 9.

[00:04:12]And if this is the cost then what is the minimum number of operations? Minimum cost to delete the entire string.

[00:04:21]So let's start with this version first.

[00:04:24]Uh the one where you delete without paying additional cost. That is in one operation you can delete as many characters as you want. So let's see how we can solve that. Now in this problem of course I I won't dive deep into why greedy does not work because you can try a lot of cases and we can talk on and on about it for why greedy does not work.

[00:04:50]In case if you think you have a greedy approach, do let me know in the comment section and I will let you know a counter example for that because in this problem a lot of people get confused and think that this is an easy problem to solve. In fact, it is not. So I will not dive deep into why greedy does not work.

[00:05:08]Let's just focus on how to solve it via DP. Even if you think that greedy works for this problem, let's just focus on the dynamic programming aspect. Now if I told you that this problem could be solved by dynamic programming. What is the first DP definition that you can think of? So the simplest DP definition that you can think of is consider any subarray I toJ. You might wonder what is the minimum cost to delete this entire subarray.

[00:05:43]That is the most natural DB definition.

[00:05:46]Right? So you define something like this. DP of I J is the minimum cost to clear the string I toJ when it is viewed in isolation. Now what does this isolation keyword mean? You must have realized that in all of the DP problems that you have solved so far. Whenever you define a 2D DP like so and if your 2DP represents I and J, you always view this array I to J in isolation. That is you don't care about what all elements are to the left hand side, what all elements are to the right hand side and then you try to compute the answer for the smaller subarrays and then you merge them to find the answer for the bigger array.

[00:06:31]Now this is the obvious DP definition that you can come up with. Sure. But then how do you do the transitions?

[00:06:38]Because when you try to do the transitions you will run into some issues. And what are the issues? So if you look at this example that we discussed earlier, let's say for this example, you can notice that if you delete some string in between like if you delete a set of identical characters, then there will be gaps created and then one segment can now start interacting with the other segment but then there is also a gap in between. How do you account for the for that gap? Right?

[00:07:13]So the first thing that you might try is okay you say that let me try if I want to solve for assume that this is your entire string I to J that is being weird in isolation and there could be other characters to the left suppose there are other elements to the left over here we don't care about them and there are other elements to the right we don't care about them and we want to find out the answer for this now can we write it as the formulation of some subpros. But of course those sub those sub problems should be inside this bigger subarray only. Now the most obvious idea that comes to mind is okay what if I make a choice on the first operation.

[00:08:01]So you might wonder that the first operation uh like let's say the string is something like this a a b b c d and b then you might wonder okay if I apply the operation the first time over here. So you say you might want to delete this. Then if you if you delete this then the cost is one and your answer is DP of this segment.

[00:08:32]Right?

[00:08:34]So far so good. But then you might also make another choice. And the second choice is that what if you decide to delete this.

[00:08:43]Now the real problem arises. That is if you want to apply your first operation on this subarray then your DP becomes almost impossible to solve. Why? Because if you delete this then this is isolated over here. This is isolated over here.

[00:08:59]So isolation is good. In DP problem isolation is good but here it is it will actually lead to inconsistent result because there could be instead of a C it could be an A over here. And then you can see that if you solve it independently then your logic is incorrect because this A interacts with this A because once this B and B and B clears out all these three A will come together. So there is no strategy that you can think of to effectively manage both of these together because you can't just keep on removing elements and then combining them then it won't really be a DP. it will be an exponential solution costing you 2 ^ n. So of course we we were trying to apply some choices to the first operation, right? Choice to the first operation. We wanted to know where to do the first operation. And you can clearly see that if you decide to do the first operation in the middle of a subarray, it will create these gaps and it is very difficult to fill this gap with DP. So that's why we have to be a bit smart about it and think of it from a different perspective. So this is kind of like thinking outside of the box because in DP there is no rule book that says that you always have to apply your choices on the first operation. As long as you apply the choices in a way that is that covers all the possible scenarios then you are good. So if you have watched my previous videos you will know that I always recommend starting by in DP problems I always recommend starting small that is think about what if you have already computed the answer for this prefix and you are trying to append a new element over here. So suppose the element that we are trying to insert is X. Then instead of applying the operation, instead of applying the first operations by ourself, let's be a bit creative and let's focus on this x.

[00:11:09]Now we are not claiming that we will apply this apply the first operation on x. That might not always be the correct choice. But we are saying that eventually we will apply the operation on this x. So when we do apply this operation, what would happen? Either either you would apply when x is alone either you apply when x is the only remaining element or or the left element or the current element that is to the left of x that is not equal to x. So you have to apply it alone.

[00:11:46]Otherwise if you if you don't want to apply it alone then you it means that on the left hand side another x should appear because there has to be so either this x appears alone when you are applying this operation or it appears with a series of x x x here x here and then they are all together and then you collapse all of them at once.

[00:12:15]This means that if you want to apply it to a series of X and you know that that series of X can come from the left hand side only. Why? Because X is the last element of your array. So let let us first locate where are the X's present in the array. So suppose this is the last element X and suppose X is also present here. X is also present here. X is also present here and X is also present over here. Then if you now focus your attention on the last element instead of trying the first operation.

[00:12:49]So notice the shift. This time we are not talking about operations. This time we are talking about the choices that we want to make eventually on the last element.

[00:12:59]Then you can see that either you apply the operation on X in isolation and if you do that then your answer would be it the cost would be 1 and your answer would be 1 + DP of I J minus 1.

[00:13:16]Why is this true? Because even if you apply this operation in future it will still cost one. So why not just do it as the first operation and then you can see that you now have a sub problem that is you are now in interested in the answer when you only have this segment available to you. So so far so good. But now what if this x is not deleted alone? In that case there must exist some left neighbor of x. And what can that left neighbor be? It could either be this element or it could be this element could act as the left neighbor because it is not necessary that both of them should be taken.

[00:14:05]Then this can also act as one of the neighbors. Actually maybe in this case it might be necessary but doesn't really matter but and then you can this could also be the next neighbor.

[00:14:24]Now by just by looking at this example some some of you might feel that if all of these X's are present then maybe the optimal strategy is to wait for all the X to come together and then combine them and then do the deletion at the same time. But actually that is not correct and that is a good exercise for you to find out why why the optimal strategy for waiting all of the excess to come together and only then delete them is not a good strategy. So I do have a counter example for that but I recommend you to try to think why that grad strategy is incorrect and if you are not able to find it I'll send share it in the YouTube comment section.

[00:15:06]So assume that you decided that this is the X that you want to merge with that is when when the operation is applied on this X this X was on the left hand side of it. Now you can see a beautiful structure coming out of it that is if you really want this X to be on the left hand side of this X then you have essentially created a boundary.

[00:15:35]So this is one end of the boundary. This is the other end of the boundary. And all the elements that are in between they are now isolated because they cannot interact with elements on the left hand side or on the right hand side. Why? Because for them these two axis need to come together. So they'll act as the barrier.

[00:16:01]So then you can say that you have to clear out this entire string somehow and you have to do it in isolation.

[00:16:11]And what is the minimum cost to clear out this entire string in isolation?

[00:16:16]That is nothing but if this index is if this index is K then that is nothing but that would be 1 + DP of K + 1 and J minus one and then the left part is of course also in isolation so plus the left part. So the left part would be DP of I to K minus one and then you iterate K over all the possibilities of X that exist in the array.

[00:16:53]So now you see that we are indeed able to come up with the DP transitions because at first glance when you define this DP it looked almost impossible to solve. And why was that? Because we were trying to do the first operation by ourself. We had to think outside of the box and we had to make the choices on the last element and just by looking at that last element we were able to create isolations and that is the big idea behind interval DP. So the technique that we just discussed is known as interval DP. And in interval DP, your aim is to make sure that if the problem is trying to tell you that after a segment is deleted, if the problem asks asks you to combine the left and right segment, your goal should be to avoid this combination by being smart about the DP choices that you make so that you create isolation. You create some barriers such that this part can be solved via DP independently and the left half can be solved via DP independently.

[00:17:59]And how how did we prevent the merging?

[00:18:02]By adding a barrier over here from X over here and X over here.

[00:18:09]So that's all there is to interval DPU.

[00:18:12]So maybe you might not have been able to come up with this uh trick by yourself or maybe you have. But either case now that you know the trick the next time you encounter such a problem you know that you have to think from both the perspective because of course in some of the problems this trick works that is try to make the first choice and then recurse on the uh remaining segments that you have. But then if it is getting difficult for you and these segments start interacting with each other may don't make the first choice of the operation but instead focus on an element that you are trying to append because if you think about it the strategy that I just discussed it's it's not that counterintuitive because in prefix DP you have already seen this trick wherein you try to analyze how to refresh your DP values whenever you append an element x to the array.

[00:19:11]So just by making the choices of where where the next where the left neighbor would be you have essentially created barriers and isolations. And then now you can see that this problem can actually be solved via dynamic programming because once you create these barriers you are now interested in that same problem but on a smaller uh subarray.

[00:19:34]So of course the time complexity would be O of N cq because there is 2D DP and then to create the barrier you will have to evaluate all the X's that are present and in the worst case the entire array could consist of X but that's all right that is the standard time complexity of interval DP. So let's quickly look at the implementation for this.

[00:19:59]But before we do that, let uh let's first focus on how how we can compute that the answer for this test case that we are just discussing this one a b c d c b a because even though we have theoretically solved it on paper if I actually try to ask you to visualize how the dp is working maybe some of you might not be able to and for that I don't blame you because this is one of the concepts where you cannot which you cannot learn in a day or just from one video you just have to watch this video sleep on it and then come back to it a couple of days couple of months later and one day you will eventually realize and appreciate how interval DP works. So how would it work?

[00:20:50]So you see that at the end you want to collapse A and A and this is the actual correct strategy. So you would do that by saying that okay I want to find the answer to this then this element can either be collapsed by itself getting the cost of one and then the answer of this segment which will of course be more than four right or this element can be merged with this copy over here and then this element this segment has to be viewed in isolation and the left segment also has to viewed in isolation.

[00:21:31]Then how do you solve for this part B C D and B? Then same trick either this gets collapsed in isolation or this gets merged and then you solve for this segment in isolation and you repeat the process. Now one thing that you will notice actually one minor correction when we were when we were discussing the DP uh transitions and when I said that this is X over here and this is X over here. Then when you are creating this barrier so this is 1 X over here and this is 1 X over here.

[00:22:09]Then you said that when this element will be merged either it will be merged alone or it will be merged with a series of X's where the left neighbor is this element. Then when you are doing the DP transitions it actually I actually wrote something like this earlier right 1 + DP of I to K and then I wrote 1 + DP of this part this part and then I added one for this which is actually not correct. So I would just like to clarify on that because see you want to you have the series of X's.

[00:22:51]So either this element is merged alone, either this is collapsed alone or this is combined with a series of X. But when you combine it with a series of X, you actually added this as the left neighbor. But this itself could have a left neighbor, right? Then this means that this means that when you are merging this X to here, you have to find out the DP value of this entire segment.

[00:23:25]Because if you find this, if you add this barrier over here and you solve for this part independently, like you collapse this part independently, then you can notice that this x that is remaining over here, this x that is remaining over here, you can kind of assume that this is this doesn't really exist anymore. Why? Because merging merging two elements is free. Because if you want to delete D and D the cost is one but even if you want to delete D and D even then the cost is equal to one.

[00:24:05]Therefore when you decide to merge this X with this X over here you can completely forget about this X and just focus on this part. So the answer would actually be this DP of I to K plus DP of K + 1 to J minus 1. This is the actual transition. There won't be + one. Now why won't there be + one? Because if you want to add + one that is if you want to do the merging of two elements together then you would also have to consider the merging of three elements together.

[00:24:43]Right? It could also be this scenario.

[00:24:45]This x could either be merged with this this and this element. So instead of worrying about all the nc all the 2 to the power k possibilities you just forget about this x and you say that okay this x you focus on the left neighbor of this x.

[00:25:06]Now I could have edited out this part in this video but I I still want to keep this uh like slight uh deviation that we had from the actual DP transitions because this will actually come into picture when we talk about the uh next problem that is in the next problem we'll see how this merging can affect things if there is a cost associated with it that is if you want to if you want to manually do the case analys analysis then sure you could say something like if X is present over here and X is also present over here X is also present over here then when you do the merge if you say that okay I want to incur a cost of one right now then you have to consider the case of X and this X but then you also have to consider the three-length cases by yourself and the fourlength cases by yourself manually but to avoid doing that you can be smart about it and you can just say that Okay, let me focus on what my left neighbor is. And I don't care how many total elements I'm going to merge with when I'm being collapsed. I don't care how many total elements I'm going to merge with. Why? Because whatever I'm going to do, my left neighbor is will also do the same. So its DP value will incorporate all the possibilities. So I don't have to manually iterate through them. So that's why you can you just have to guess what is your left neighbor. Is it this one or is it this one or is it this one or is it this one? So now do you see why only this DP transitions without a + one is actually correct? Because if you start adding + one then you have to manually explore all the 2 to the power I possibilities where I is the number of occurrences of X.

[00:26:59]So I hope you got to understand something uh at least from about interval DP from the discussion that we have had so far. If you have if you still have any doubts about this do let me know in the comment section. Now let us look at the transitions or or actual code implementation. So we define DP of I is the minimum number of operations to reduce this substring from I to J to an empty string. This is the simplest DP definition that look like wouldn't work but then we found a way to do the transitions to make it work.

[00:27:36]Then you see that if the interval length is one there is only one possibility you have to merge or collapse it alone incurring a cost of one. Otherwise, if you have these n elements already and you want to place a a new element at the end and basically the last element would be this a of j that you have just appended. So either you decide to merge it alone in that case you pay the cost of one up front and then you focus on this left problem or you decide to merge it with one of the existing element so that once you do the merge you only have to let this element be the leader and let it do all the heavy lifting because whatever this element will do you'll simply go and attach it over here because you are planning to erase this segment completely.

[00:28:29]So either you delete it alone then this would be the transitions or if this is the X then you locate the positions of the X at the entire array and you see which one do you want to be your left neighbor. So if this is your left neighbor or this is your left neighbor or this is your left neighbor. So you try all of your left neighbor and then once you have done that the contribution would be you have to if you have decided that this is your left neighbor then this entire segment has to be collapsed.

[00:29:02]What will be the cost? That is simply DP of K + 1 and J minus one. Otherwise if you decide uh and then once you have decided that this is your left neighbor this internal segment has to collapse and then you have to focus on the answer for not just the left part because you haven't yet made a decision on what you want to do with this X. You are just merging it it with this X but then this X could further be merged into another X forming a chain. So this chain structure this is actually what is preventing that additional one to come into that picture. So if you decide to do the merge you only have to look into DP of I comma K and your answer is the contribution from the left hand side and the right hand side and whatever is the minimum you take that. So you see that the transitions and the code are so simple like one of the simplest code that you might have seen on DP but actually it's a bit more sophisticated on the logic side. But if you give it a couple of days and if you think about it and if you think about why we are not adding one and why it actually covers all the possibilities very nicely and how does the concept concept of barriers and isolation makes interval DP work you'll eventually start appreciating how clever this is and no matter how clever it is even if you are not able to come up with these transitions or these DP definitions yourself once you solve good number of interval DP DP problems you will become upskilled. You will upskill enough to solve hard DP problems by coming up with the transitions by yourself or even if you are not able to come up with the transitions at least you should be you should have a good idea of the DP definition to use in that problem.

[00:30:49]So so far so good. Now let's talk about the hard version of this problem.

[00:30:55]In this version, we have that same concept where you have to collapse the string. But then every time you do the collapse, you have to pay the cost of the number of elements that you are collapsing into square of the length. So for example, if you want to do the collapse of D and D, the cost would be four. And then if you want to collapse C and C, the cost would be sorry, the cost would be four. And here also the cost would be four. the cost would be four and the cost would be four. So the total cost is 16. I don't know if 16 is optimal or not because this is the answer for the uh this is the sequence for the easy version of the problem. Most likely the harder version also will have the answer of 16 that we'll have to see. But I hope you got the problem idea that is every time you do the uh collapse you have to you have to add the cost of length into length into your answer.

[00:31:54]Now again what is the simplest DP definition that you can think of? You will of course think of something like DP of I sorry you will think of something like DP of I like if this is your substring that you are dealing with or let's just assume that this entire thing that I have drawn is my substring that I'm dealing with and let's say that you have some additional elements over here that you want to ignore. So these are the additional elements over here that you want to ignore. Now if you define your DP in such a way that DP of I J is the min minimum cost to collapse this entire substring that we are dealing with. This is I and this is J. Then again you can apply the same trick where you focus on this element.

[00:32:41]If the element at this location is X then you have multiple choices. You can either try to delete X in its own separate group that is you can delete X alone by paying a cost of 1 into 1 or you can merge this X with one of the existing copies that are present in the array.

[00:33:06]So for example, if you decide to collapse this X with this X and there could be more X to the left hand side of it. But all we care is that either this element will be collapsed alone or there will be at least one element to the left hand side of it. So the element that is on the left hand side of it, it could either be this one or this one or this one and so on. Then if you have already decided that this element is going to be present on the left hand side of this X when the collapse happens then you can see that you have isolated this problem because this subarray is now isolated. So you can compute this DP value and then you can compute this DP value because why not this one? Because you you also have a choice to continue this chain forward like you can create this chain and then this chain. You don't necessarily have to collapse these two elements together.

[00:34:13]But now you will notice some limitations in our approach because in the previous version we said that if you want to collapse these two x together in the previous version we said that if you want to collapse like let's say this and this x together then sure you have to compute this segment in isolation but then you can simply ignore this element.

[00:34:43]because this can this will be basically a free loader that can attach itself to this X whenever the collapse is happening for the substring of which this X is a part of. But now this cannot be a free loader anymore because it contributes it adds an additional cost because it is present to the left hand side of it. So this time we can't simply ignore this and we compute the DP value of this and this and then add them. So then you have to kind of remember that there is one free loader at the end.

[00:35:20]That is you have to remember that when you are computing for this subarray you have to remember that one X came to you and they will stand right next to you over here when the collapse is happening. But then when this process is repeating when you do the DP on this inner subarray you will apply that same technique and you will you will either decide to collapse this X right here alone or you will try to merge it over here like let's say if this is also X then again you have to remember that there is some X that are remaining at the end that are waiting to be collapsed with you.

[00:36:02]So just tracking the DPI is not sufficient anymore because with DPI you are only able to compute what is the cost of this subarray in isolation.

[00:36:15]But now none of these subarrays can actually exist in isolation. Because if this copy is X, this is another copy of X and then this is another copy of X.

[00:36:26]Then one sequence of collapse is that this this and this gets collapsed together. And how would you achieve that sequence? When you start at this element, you say that okay, I want to collapse it in combination with this. So this this small subarray has become isolated which is good. But then you have to remember that at the end two copies of X are remaining. Then when you want to transition from here to here you have to remain that you have to remember that not just one copy but actually two copies are remaining. So this time you don't you can't solve the problem just by tracking DPI anymore. You also have to track an additional parameter. And what is the additional parameter? The additional parameters are how many copies of the last element because we were applying the DP on the last element and this is the standard trend in prefix DP that is you have some array and you decide what happens to the DP values when you try to append an element at the end. So this means DP I J and you also have to introduce an additional parameter which is equal to C and this C would denote how many extra copies of this last element did you receive from the outside world. So we can have this DP definition that DP of I, J and C is the minimum cost to clear S str I to J is still in isolation but the only interaction that it has with the outside world is that after the outer world has collapsed it will receive a series of identical elements that is equal to X.

[00:38:01]So if it is X then it will receive C copies of X at the end and then when you are making the choices your choices does not look like collapse it alone or merge it with something. Your choices will instead look like collapse it with the set that you have already received so far from the outer world or you extend this set and you merge it with the inner world.

[00:38:28]So DP of I J C is the minimum cost to clear this S str in isolation when you are receiving C copies of the last element from the outside world.

[00:38:38]So now let's look at the implementation for this.

[00:38:42]So you now maintain a 3D DP instead of 2D DP. And again the definition is same that DPig is the maximum points or the minimum cost when you want when you want to collapse the entire array I to J in isolation when you are receiving C copies. And what would be the answer?

[00:39:05]The answer would be on the original array you are not receiving any copy of the last element from the outer world. So that's why it is dp of 0, n minus one and zero. And how do you do the transitions? So the transitions are simple. You know that each dpi when you make this choice to merge with a single element, you are now trying to ask that same question but on a smaller subarray. So that's why if you populate all the DP values in increasing order of length then by the time you reach a bigger array you will have the answer for all the smaller subarrays along with the possibilities of appending some copies of the last element. So that's why you iterate over all the element and suppose now you are dealing with the range I to J then if you are receiving C copies from the outer world then you can either decide to collapse everything right now. So if you are solving for this part then you have received C copy of X on the right hand side where X is equal to the last element and so you have received C copies of of this then you can merge all the copies or and collapse them together right now and be done with it and if you do decide to do that that so first of all like if the length is one of course you have no choice but to but to collapse all the copies that you have currently. But if the length is not one of the subarray, then you can either decide to collapse all the copies that you have already received so far including the last one.

[00:40:44]This is the point. This is the cost when you try to do that collapse right now.

[00:40:50]Or you can decide to continue this chain forward and you can locate the next x and all possible x actually not just the next x. So suppose the next X is here and here you can decide to carry forward. So you already received C copies from the outside world then you can make it a C + one copy then you can transfer the responsibility to this X.

[00:41:12]So that's why you find out where is X located in this array and then if once you find out the X you say that okay I I want to merge my C copies from the outside world and then one copy from here and I want to isolate this subarray in between. So that's why you call this.

[00:41:32]So let me give you a bit more clear picture.

[00:41:38]So suppose this is I and this is J and you have received three copy of A of J from the outside world and let's say that this is K. This is the position where X is available over here and X is also available over here. Then you can say that I want to transfer my C copies from the outside world and the one copy that I already have to this element and I want to be merged and collapsed together with this element. So this means that this array becomes isolated and this array is nothing but k + one and j minus one and then once you have merged it you actually call it for this entire segment not just this segment. Now you can see why the thing that we discussed earlier that is uh you don't have to merge immediately like you can propagate these copies around was important because if you have received C copies then this chain can continue this chain can continue so that's why it it will be I to K with C++ one copies contributing from the outer world or if you decide to or so on the left hand side it would be I to K with C +1 copies and on this part you see that you are not contributing any copy of the last element. So that's why that is K + 1 to J minus one and you take the max of it. So why is it max and not min? Because uh this version of the problem was about maximizing the profit and that's why but if you if you want it could be minor does not change.

[00:43:19]So of course the time complexity is now O of N ^ 4 and there is no way to optimize it and the time complexity of the previous version was O of N ^ 3. So these was these were the basic ideas behind the interval DP. Now now if you try to think about it although we have solved the problem it is still kind of like magic right? If you think about it like especially the length length square case right. If I had asked you to solve this problem directly like if I asked you to solve this problem directly where the cost is equal to length square then if you and if I told you that this is the actual DP definition that would be used in this video sorry this is the actual DP definition that would be used in this problem you wouldn't believe me at all like how come how in the world like you pulled this DP definition right like this seems So out of the blue. But if you solve this problem after you have solved the first problem with the cost as one regardless of how many elements that are there, then you then everything makes sense, right? Then everything makes sense that when you are merging these element, you cannot merge for free anymore. So you have to remember how many copies wants to be merged with you.

[00:44:43]So this is a nice follow-up to the original problem. And if you solve the original problem, this makes sense, right? It's not that difficult to grasp.

[00:44:51]But what if you are solving this problem alone and then you encounter this DP definition. So in the remaining part of the video, I want to discuss some more on this like some more intuition behind this and why these kind of DPS work right. So if you look at this DP definition, what is odd about it? So in most of the problems that you must have solved so far especially for subarray DP you will I'm pretty sure like there is hardly any case where you have encountered something where you are not viewing this subarray in isolation because here you see that it is now not exactly in isolation. Yes I2J is in isolation but then it is also interacting with the outside world with a parameter called C.

[00:45:38]And there are not a lot of DP problem at least that I have seen that uses this pattern wherein the sub area is not in isolation but interacts with the outer world.

[00:45:50]So this might seem very counterintuitive to you because in a lot of DP problem it is something like okay what is the answer for I2J when the sum of these elements in I2J is S and then the prefix maxima is P and then the largest value that you have placed is L and so on. But whatever happens happens inside this array. But a lot of you uh might be seeing this pattern for the first time where you are receiving contribution from the outside world. So like what exactly is the intuition behind it, right? And like are you really sure that you have not seen this pattern before? So let's talk about that. Now a couple of days back I uploaded a video on my YouTube channel uh talking about dynamic programming on trees, right? And I want to connect this to how we solve DP on trees. So because if you think about it, this is like this is like a paradigm shift to a lot of you because most people usually deal with with dynamic programming on subarrays by ensuring that you only look inside the subarray and not outside. But if you remember my video on DP on trees, actually DP on trees has been using this pattern from the very beginning. And in fact you must have already solved a lot of problems that use this pattern.

[00:47:19]Why? Because if if you remember in DP on trees I told you that when you perform a DP on tree you have to take care of two things. So one is that when you add a child when you add up append up sorry when you add a parent to a node you you want to make sure that the DP value of the children are not invalidated and then you also have to make sure that when you add a parent. So suppose you are adding a parent for this node. If you are adding a parent over here, then if you want to make sure that the DP value of this is not invalidated, then you have to track the parameter of the parent right from the start. You can't simply append uh like attach a parent over here. So if you remember there is there was a video about getting an edge bonus if X and X were equal. And in that case we had said that if we forget the value of the parent then whatever we have done the computation on this child that will actually be incorrect. And there was also another problem where you wanted to color the nodes in red and black and even in that case we had said that if you ignore the parent then the probability of this node being colored as red that would actually be incorrect.

[00:48:42]So that's why you had to track another parameter which represents that what is the minimum number of rounds to color this sub tree when it parents when its parent displays red versus when its parent displays blue.

[00:49:01]So this DP on trees actually has been using this pattern and I'm pretty sure you must have also used this pattern. So so this is actually not that big of a deal. So subarrays can actually take contribution from outside world. It's just that there are not a lot of easy problems on this topic or maybe they are maybe I'm I'm missing something but uh yeah there are not not a lot of problem that has this concept. So that's why it might seem uh a bit weird to you like how like how come this DP definition is making sense right and the last thing that I want to discuss is like sure like this DP is there but then how did we get the intuition for this DP by solving this easier version right and from there we concluded that you want to merge X to here and then to here and then to here and so on. But if if the easier version did not exist, we would have had a hard time coming up with the solution. So I want to show you another intuition behind why this DP makes sense even if you do not know how to solve the easier version of the problem. So let's see how we can do that. So if I told you that the cost is length into length, then how would you actually start approaching the problem? You would start by picking this subarray from I to J and you will just define your simple DP. DP of I J represents what is the answer when this subarray I2J is viewed in isolation. Now I I have a question for you. Can you actually solve this problem without a 3D DP?

[00:50:43]So regardless of the time complexity, can you actually solve with solve it by just storing two parameters in your DP value? So at first it might look impossible now that you have seen that you do need to track the number of copies that you receive from the outer world. But it is actually possible if you think about it. For example, let's say if you want to apply the DP on this X, right? And suppose these are the copies of X X and X is available over here and X is available over here. Then I want to solve the problem by just tracking two DP parameters. And how do I do that? For this element, I can make a choice. I I can either collapse it right now by paying a cost of one or I can decide to merge it with one of the elements and I can collapse it in batch of two. So the batch size will be either one or two. But if the batch size is two then it means that this X gets merged with one of these elements on the left hand side. So I can try this possibility.

[00:51:50]So if I try this possibility and the batch size is two then the cost that I would have to pay would be two square plus now you see that this is isolated I can solve independently and this entire thing is isolated we can solve independently. Then this is one possibility but then you can also decide to merge with this this because this and this creates a batch size of two. And then if you do that then this is isolated and then this is also isolated.

[00:52:20]You can solve it and then you can repeat for this and then you can repeat for this. So looks like that it should theoretically work with just 2D dp parameters. So what is the bug bug here?

[00:52:32]The bug here is that you are only counting the batch size as two but but the batch size could also be three. So if the batch size is three and if X is available over here, X is available over here and here and here and here then you have to select three elements out of it into which you want to merge the X and then you can isolate it without tracking any other DP parameter. So first you have to do NC zero operations and then you have to do NC1 operation and then NC2 operations. Basically you are figuring out how many of these X's like which which of these two X's will you combine this X with to do the final collapse. And once you have decided that then the sub areas that are in between they truly become isolated without requiring any additional DP parameters.

[00:53:21]But then if you repeat this process you will get this sum and this is nothing but 2 ^ n. And that is why if you do not track a third parameter the time complexity of your DP will be 2 to the power n but it will indeed be solvable.

[00:53:35]And that is where the intuition for the third parameters comes in. Because if I told you that okay you have to explore all these 2 to the power n subsets you will now realize that for exploring all the 2 to the^ n subsets does it actually matter whether you took this and this and in the other case you took this and this. Why? It does not matter because all it all the only thing that matters is how many elements that you have in your subset not the actual position of the subsets.

[00:54:05]So that's why the last parameter that you see over here in this DPig and C this C is nothing but the subset DP that you are doing over the last parameter of 2 to the power n subsets and that is the intuition behind what why the last parameter comes even if you ignore the easy version of the problem. So this was it about the interval DP and uh okay so if you have really understood everything so far let me give you another version of this problem and let me know in the comment section how would you solve it and the solution to this problem you can only see if you have been paying close attention. So this time I say that the problem setting is same but now instead of the cost uh so previously we saw that the cost function was one regardless of the length. Then we saw that the cost function was length into length right the cost function was length into length and this this was for n cube and this costed you n ^ 4. Now this time I want to say that the cost function is just length that is you can collapse L characters if they are identical by paying a cost of L. Then can you tell me how do you compute the minimum cost to collapse all the entire string. So think about it and do let me know in the comment section how would you approach this problem and uh if you have any other questions about this approach do let me know in the comment section and I agree that this is a bit difficult topic and it is very difficult to wrap your head around it but u once you try out all of these cases in paper on paper and you see why these all 2 to the^ n subsets of possible choices of the last elements are happening then you can realize like what is what is actually going on behind the scenes and even though it's a difficult problem I would still encourage you to try to try to like solve try to take any random string and see how DP actually processes all the combinations that that can happen in an optimal order in just O of NQ or O of N to ^ 4. So this is a very good exercise in learning dynamic programming even if you won't actually apply interval DP in future. Now again uh coming back to my original question like I said that one of these problem is from lead code one is from code forces. So do let me know in the comment section which one do you think is from where and what is the expected difficulty rating that you would assign to this problem. Thank you.