Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only if it is a palindrome (if we can read it in the same way from the front and the back).

For example the array 1 1 5 9 5 1 can be deleted in two steps. Step 1: Delete substring 5, 9, 5. Then delete the remaining substring 1, 1, 1. We only need to return 2, the number of steps.

My idea is to use dynamic programming technique. Our state would be $DP[L][R]$ meaning the minimum number of steps to delete the substring in range $[L, R]$. However I can't really work the transitions, since there can be cases when our front element will merge with some element in the middle and with some elements in the back, so I don't know how to cover all transitions between different states.

  • 1
    $\begingroup$ Or delete the first 1 or the second 1. Then delete the remaining substring 1,5,9,5,1. $\endgroup$ – John L. Mar 6 '19 at 14:34
  • $\begingroup$ Did you create the problem by yourself? Otherwise, can you edit the question to add a reference? $\endgroup$ – John L. Mar 6 '19 at 14:37
  • $\begingroup$ I saw this problem couple years ago, yesterday I saw a similar problem that reminded me of this problem for which I still don't have a solution. I don't keep the link for the problem. By the way, the problem is only asking for the minimum number of steps. $\endgroup$ – someone12321 Mar 6 '19 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.