Hey there and welcome back.
Let's now discuss the tabulation approach for solving palindrome partitioning two.
Now we're going to discuss two approaches.
Over here we'll discuss the approach where we are going to use a 2D DP array.
But after this we will also discuss the approach where you can solve this by just using a one dimensional
DP array.
So let's get started.
Now first let's spend some time and build the intuition which is necessary to solve this question.
So again remember over here the question deals with substrings and not with subsequences.
So this is an important thing to note.
Now let's take an example.
Let's say the string at hand is a b a b a.
Now over here we see that the first and last characters are equal.
And we also see that the middle part over here is a palindrome in itself.
So therefore if this is the case, we can conclude that the string at hand which is a b a, b a, is
a palindrome and therefore no cuts are required for a, b a, b, so zero cuts are required if this
is a string.
Another observation that we can make is that if the string that we are considering consists of only
one character, then because this over here is a palindrome, we would need zero cuts.
Now let's take another example.
Let's say the string that we're considering is a, b a, a, c.
Over here, we see that these two characters are not equal.
Now, to identify the minimum cuts required for this problem, let's think of it in two steps.
First we are going to make one cut.
And then we are going to analyze the subproblems.
Let's take some time to think about this.
First let's discuss making one cut.
Now the problem is a b a, c.
And we are going to make one cut in a way that this string over here is divided into two sub strings
or sub problems, where each sub string is a sub problem.
Now what are the different ways in which we can do this.
So I have a b a c over here.
And I can either do the cut over here or over here over here over here.
So depending on where I do the cut the two sub strings are a and b a c.
If I do the cut over here a b and a c if I do the cut over here and in a similar manner, I could get
a, b a and a c or a b, a, a and c.
Now let me write the indices over here I have 01234.
Notice that if I make the cut at index zero I am getting this scenario over here.
If I make the cut at index one, then I'm getting this scenario over here where I have a B over here
and a C over here.
Similarly, if I do the cut at index two, I get a b a and a C.
And finally, I could also make the cut over here at index three, which would give me a, b, a, a
and c.
So these are the possible ways of making one cut.
Again these indices over here are correlated right.
So we have zero over here and zero over here.
And the ways in which we can cut or the places where we can make a cut ranges from zero up to three.
Or it goes from zero up to this four minus one or I to J minus one.
Where this over here is I, and this over here is j.
So it goes from 0 to 3 or from I to j minus one.
So we have discussed the different ways in which we can make one cut for a problem given to us.
Now let's take a look at the subproblems in these different scenarios and analyze them.
Now if the string is a, b a, a, c, we already know how to go over all the possible substrings by
iterating over the diagonals in this depee table over here.
So first we would go through these cells.
Then we would go through these cells and proceed in this manner.
So we have already discussed this multiple times.
Now let's make an interesting observation.
Notice that if we fill this depee table lengthwise and each cell stores the minimum cuts required for
the substring that goes from index I to index j, which is given by the row value and the column value,
respectively.
Then we would already have the answers to these subproblems, because over here.
Notice that the length of this problem over here is five, and the length of the subproblems over here
is less than five.
For example, the length of this string is one and the length of this string is equal to four.
And because we are going lengthwise, we would already have calculated these before we get to a problem
of length five.
Because remember these strings over here have length one.
These have length two.
These have length three.
And it goes on in this manner.
So if we fill this depee table lengthwise we already have the solution to these subproblems.
And we can use that to identify the way in which this problem over here has to be cut, such that we
can partition it into substrings where every substring is a palindrome in itself.
Now let's take a pointer k to iterate over these values over here.
So k will go from zero up to three and then depee at ij in this table over here.
It's going to equal depee at I k plus one plus dpi at k plus one j, because that's what's happening
over here.
For example, this over here is actually DPI at zero zero because k is equal to zero.
And then this over here is DPI at one.
And then over here we have four or this problem over here is DPI at zero one.
And this is DPI at two four.
Right.
Because we have already stored these in the DPI table over here.
We can just make use of them.
So when we are doing a cut at index k we are doing one cut.
So that's why we have plus one over here.
And then we just need to know the minimum number of cuts required for the two sub problems at hand,
which is something that we have already calculated.
And we can get that from DPI at I k and DPI at k plus one j.
And because k can take different values, we are going to identify the value of this dpi at I k plus
one dpi at k plus one j.
We are going to identify the value of this for these different values of k.
So we are going to get four values and then dpi at I, j will take the minimum value of these four values.
So this is how we are going to fill the DPI table over here.
And this is going to be much more clearer when we do a dry run of this approach in the next video.