Welcome back.
Let's now write the pseudo code for the tabulation approach that we have just now discussed for solving
palindrome partitioning two.
So we have this DP table over here.
And we know that we have to fill it lengthwise.
And we have done this multiple times.
So we can say for length going from one to n and for I from zero to n minus l and j is equal to I plus
l minus one.
So this is something that you have seen multiple times.
And this nested for loop will help us go lengthwise.
Now initially we will check whether I is equal to J which represents these cells.
And if I is equal to j we are dealing with a substring of length one.
And we know that a substring of length one is a palindrome.
So we can just fill zero over here.
Now we proceed.
And if this is not the case we are going to check whether the character at index I is equal to the character
at index j.
And if these are equal, we are going to check whether dp at I plus one and j minus one is equal to
zero.
This means that after we remove these two characters from the string that we are considering, is the
remaining part a palindrome or not?
Or do we just need zero cuts for the remaining part?
So if this is equal to zero, it would indicate that the remaining part is a palindrome, which would
mean that the total substring that we are considering is a palindrome.
And therefore we can say dp at I, j in that case is equal to zero.
Now we proceed, and if this is not the case, then we are going to say dp at I, j is equal to j minus
one, which would indicate the scenario where we would need to do a cut at every possible place.
So this is the maximum value that dp at I, j can take.
And then we are going to take a variable k which goes from I up to j minus one.
And then for each value of k we are going to compute dp at I k plus one plus dp at k plus one j and
dp at I.
J is going to take the minimum value among dp at ij and this value over here.
So initially dp at I, j took the maximum value.
And then when k is equal to I, we will get a value for this.
And between the initial value and this value dp at I, j will take the minimum value.
Then k will take the next possible value among these possible values.
And we are again going to compute this value.
And in this manner we are going to evaluate all these possible values.
And finally dp at I j will take the minimum possible value.
Or we will make the cut at the place where this over here is going to take the minimum possible value.
In this way we will fill dp at ij and then proceeding from cell to cell, we will fill the DP table
over here.
Finally we will have the answer in this cell.
Therefore we will just return dp at zero n minus one.
So this is the pseudocode for the approach that we have discussed which can be used for solving palindrome
partitioning two.