Beautiful problem on Dynamic programming.

 Problem Statement

Given a string we can select any substring consisting of all equal characters and remove it and this will be counted as one step.you need to find minimum number of steps to remove the string completely.

Now a greedy approach can be deleting the largest substring consisting of equal characters,although it seems accurate but it will easily fail.

Consider string "aaabaa" so greedy will delete "aaa" first in one step,then "aa" in second step and finally "b" in third step giving total of 3 steps but optimal is deleting "b" in one step and "aaaaa" in second step giving 2 steps.

So either the string at current index will be removed individually or will be paired with some other character at index  greater than current index which is equal to it.

Let the string be str[low...high] where low=0,high=n-1 and n is length of str.

Let our recursive function be func(low,high)

So the recursive function will be called in 2 steps:-

1)So when current index is deleted individually we used 1 step and new problem we created 1+func(low+1,high).

2)When current index is joined by another character equal to itself we need to delete everything between those two characters which we are trying to pair first and also try to continue to pair on further.

New subproblems are func(low+1,nxt-1)+func(nxt,high).

The second one is tricky but suppose we try to pair str[low] with str[nxt](we can only pair if str[low]==str[nxt]) so the call to func(low+1,nxt-1) tries to ensure everything is deleted between indexes low and nxt recursively. We pass index nxt to func(nxt,high) just to carry the process of pairing further.

Consider string  str="abaca" 

minimum steps is 3 when b and c are deleted individually and then all "aaa" are deleted.

let's see how 3 "aaa" are brought together by function.

So consider func(0,4) the for loop will be called to match every character from 1 to 4.

str[0] will match with str[2] as both equal and func(1,1) will be called to delete everything between and then func(2,4) will be called.In func(2,4) focus again on for loop part,now str[2] will be matched with all characters from str[3] to str[4] and obviously str[2] will again match with str[4] calling func(3,3) and func(4,4).

So inside the for loop the first function is to clear everything between  matching characters and second function is for adding more similar characters to sequence.