Let's now memorize the recursive solution that we have just now discussed.
So in the recursion tree over here notice that one plus AC.
So this is happening over here as well as over here.
So the sub problem AC is being computed multiple times which is also the case over here.
Now if you had a more complex input you will see this happening even more number of times.
So there are overlapping subproblems.
And that's why by just adding a few lines of code and memorizing the recursive solution that we have
written, we will be able to significantly improve the time complexity of the solution.
So let's get started.
Now in the recursive approach, we had used a function called ispalindrome to check whether every substring
was a palindrome or not.
But over here, before we memoize the recursive part, which is what we have written in the previous
video, let's also change the way that we are going to check whether a substring is a palindrome or
not, and we can do that because we have discussed this approach multiple times previously.
So initially let's build a 2D array called is palindrome.
And we will in this array store values true and false for every possible substring of the given string.
So if a substring is a palindrome we will store true.
Otherwise we will store false in this 2d dp table.
And then we will just use this to check whether a substring is a palindrome or not.
Now once we have done this, let's get started with the memoization approach.
So what we will do is we will have another DP table for this.
And for every substring which starts at a start index and goes up to the end index, let's store the
minimum cuts that would be required for partitioning this substring into sub strings, where each substring
is a palindrome in itself.
So we are going to store it.
So for example, when we compute the number of cuts for a c we are going to store it.
And when we encounter it the next time we will not go down over here and compute it, but rather we
will directly return the value by just reading it from the DP array which we have over here.
So as we've discussed for this again we will need a 2d dp array.
So this is the memoization approach.
And as you can see we will just need to add a few lines of code which is to create this DP array.
And then after checking the base case before we implement the recursive case, we will check whether
the value is already computed and stored over here.
And if that is the case, we will just retrieve it and return the value.
And if that is not the case, we will proceed and calculate the value and store it in the DP table before
returning the value.
So this is the memoization approach.
Now let's also try to think of the space and time complexity of this approach.
So as we have discussed.
So we are initially going to build a 2D array called Ispalindrome.
Now this over here is going to take space of the order of n square.
And the time complexity for this operation is also going to be of the order of N square.
Now we have discussed this multiple times previously, so I'm not going to repeat it over here and over
here for this part.
For this 2D array we will again need space of the order of n square.
And the time complexity for this is also going to be of the order of N square.
Now why is that?
So we know that for a string of length n, there can be n into n plus one by two substrings.
So if you expand this, you will have an n square term.
So we can say that this over here is of the order of n square.
So for a string of length n, the number of substrings that can be formed is of the order of n square.
And because we are storing every subproblem that we compute, we are going to process a substring only
one time.
And therefore, because the number of substrings is of the order of n square.
So that's why the time complexity of this part over here is also going to be of the order of n square.
So the total time complexity is this plus this, which ultimately is of the order of n square.
And the total space complexity is this plus this, which again is of the order of n square.