Question regarding Count palindromes (Practice Easy)

Count Palindromes

Each palindrome can be always created
from the other palindromes, if a
single character is also a palindrome.
For example, the string “bobseesanna”
can be created by some ways:

  • bobseesanna = bob + sees + anna
  • bobseesanna = bob + s + ee + s + anna
  • bobseesanna = b + o + b + sees + a + n + n + a …

We want to take the value of function CountPal(s) which is
the number of different ways to use
the palindromes to create the string s
by the above method. Input

The string s Output

The value of function CountPal(s),
taking the modulo of 1 000 000 007


0 < |s| <= 1000 Example

Input: bobseesanna

Output: 18

I’ve been struggling through this problem for quite a few days. I know it must be DP but somehow I couldn’t find a way to formalize the recursive formula. The only thing I have so far is for the base case, when the length of the string is 1, then there is only one way. Could anyone help me understand this problem? I really don’t want to look at the solution because by doing that I won’t learn anything. Any suggestion or idea would be greatly appreciated.


What you think about this idea (first thought)?

Find all the palindromes that start at position 0. For each such palindrome ending at position x find

CountPal( s.substring(x+1) )

this is a very tough problem sorry i cant solve that problem.

Thanks. I will try out this idea.