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
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!