Let's now write the pseudo code for the second tabulation approach for solving palindrome partitioning.
Two.
The first step for this approach would be to build a 2D array called is palindrome.
And we will make use of this to check whether a substring that we are considering is a palindrome or
not.
So again this is something that we have done multiple times previously.
So we are not going to focus on this over here.
So once we have built this 2D array called is palindrome.
We will proceed with this part over here.
So as we have discussed initially we will just consider this string.
Then we will consider this string.
Then we will proceed and consider this string and go on in that manner.
So notice over here in each of these cases the start value is zero.
But the end value is getting moved.
And in that manner we will be considering strings which are bigger and bigger till we reach the original
problem.
So for this we will have a for loop and let's use the variable end.
So the variable end will go from zero up to n minus one.
Now notice that for a string that we are considering, we can find the maximum number of cuts by just
saying that cuts is equal to end.
For example, if you are considering a, b, a, and at this point n would be equal to two and the maximum
cuts that we can do over here is one two.
So the maximum cuts for a substring is equal to end.
Then we would need another variable.
Let's call it start.
And start will take the values from zero up to end again.
Why is this required.
Because remember let's say we are dealing with this substring over here.
Remember we had a start variable that was initially pointing to index zero.
And then we would move it to index one and then to index two.
And then to index three.
And at each of these points we would check whether the substring from start to end is a palindrome or
not.
So we have seen this previously in the dry run.
So for this we have for start from zero to end.
And then for each combination of start and end, we will check whether the substring from start to end
is a palindrome, and if it is a palindrome, we will try to calculate the number of cuts required for
this scenario, which would equal one plus depee at start minus one.
Now this over here.
This one over here is because we are making a cut.
Let's say we are considering a b a a, and when start is equal to two and end is equal to three, we
see that this is a palindrome.
So we see that let's say start to end is a palindrome.
And in this case we would make a cut over here.
And we don't need to do any cuts in this part because this is a palindrome.
And we have to do one cut over here.
That's why we have one over here.
And then we need to know how many cuts would be required for the previous part, which is DP at start
minus one.
That's how we are getting one plus DP at start minus one.
And then we also could do a cut over here.
So that's why cuts is equal to minimum between cuts and one plus DP at start minus one.
Because we are considering all the possible ways in which the string towards the right is a palindrome.
And then once start, has taken all the values from zero to end, whatever value is there in cuts would
be the minimum number of cuts required for a string that goes from zero up to end.
Therefore, over here we can say dp at end is equal to cuts, and in this manner we will be able to
fill the DP table over here.
And finally we would just need to return the last value in the DP table, which would be our answer.
Therefore, we can return dp at n minus one.
So this is the pseudocode for the approach that we have discussed for solving palindrome partitioning
two using a 1D DP table.