Help needed with Bottom Up DP !

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!

1 Like

Let
DP[i][j] be the output of f(i,j)
Then for solving DP[i][j] you need DP[i+1][j], DP[i+2][j],DP[i+1][k-1],DP[k+1][j]
so you need all values of DP[m][n] where i+1<=m<=j+1 and i+1<=n<=j so that gives you how to solve it using loops:

for(int i=n;i>=1;i--)
    for(int j=1;j<=n;j++)
        // solve here

@sarvagya3943 , this is a standard DP problem called palindrome partitioning. For details refer to this Link . It clearly explain both the O(n^3) and optimized O(n^2) approaches.

This is just a version of palindrome partitioning. Look it up !

1 Like

Thanks,that helped!

1 Like