Problem :
Given an array of N(1<=N<=500) elements , in every move you can remove any palindromic subarray (elements of the subarray form a palindrome) . Find the minimum number of moves required to destroy the entire array .
1<=Ai<=N, where Ai is the element of the array .
I solved it using this recurrence.
Let f(i,j) represent the answer for the range [i,j].
then f(i,j) =
-
0 if i>j
-
1 if i=j
else it is minimum of these three :
-
1 + f(i+1,j)
-
1 + f(i+2,j) if
arr[i]==arr[i+1] -
\sum\limits_{k=i+2,arr[i]=arr[k]}^jf(i+1,k-1)+f(k+1,j)
Here is the top down approach i implemented .
But the bottom-up approach doesn’t seem that intuitive .
Could someone help with the bottom up approach for this ?
I’d prefer the intuition(how to think of the way to fill up the dp table) rather than the code.
Thanks in advance!