[algogeeks] Another DP Question on String Palindrom

Given a string, and split it into as few strings as possible such that each string is a palindrome.Example ABAABABA Greedy algorithm: ABAABA + B + A = 3 palindromes Correct answer: ABA + ABABA = 2 palindromes so one thing sure Greedy Wont Works here , so it sounds perfect DP problem ? Thanks

Re: [algogeeks] Another DP Question on String Palindrom

First of all for all substrings ,compute a boolean matrix ispalin[n][n] which is true if a substring from i to j is a palindrome.This can be easily done in O(n^2). Next,let min[n][n] be the dp array,then min[i][j]=1 ,if ispalin[i][j]=1