The palindromic substrings problem is a question that can be solved using dynamic programming.
But how to identify that?
Let's discuss that in this video.
Now, an important thing that you need to keep in mind is that depee is useful in counting problems.
Notice that in the palindromic substrings question, we are asked to count the number of substrings
that we can form that are palindromes from the given string.
So this is one hint that you can use to identify that this is a DP problem.
Another important thing to notice in the palindromic substrings question is that there are overlapping
subproblems.
To understand this, let's take the example where the string given to us is a, a, b, c.
We have already discussed in the previous video that we would have to check a, a, b and a b c in two
separate recursive calls to identify whether these are palindromes or not.
Again, within these two recursive calls, we will have instances where we only increment one pointer.
So over here, if we only increment this pointer, we would get a b.
And similarly over here, if we only increment this pointer, we would again get a b.
Notice that the same subproblem is occurring in two branches of the recursion tree.
The palindromic substrings question also has optimal substructure, because solving these subproblems
will help us to solve the original problem, because ultimately we are trying to count the number of
substrings that are palindromes.
So in this video, we have discussed the things that help us identify this question as a DP question.