This is a dynamic programming question:

A string y is a palindrome if yy, where yR is the reverse of y. Given a text z a partitioning of x is a palindrome partitioning if every substring of the partition is a palin- drome. For example, abal bbblalbblalblaba and aba l blbbabblababa are two palindrome partitioning of x - ababbbabbababa. Design a dynamic programming algorithm to deter- mine the coarsest (1.e., fewest cuts) palindrome partitioning of x. In the example, the second partition (3 cuts) is optimal. Analyze the time- and space-complexity of your solution