Can someone please explain the approach for this problem. The approach in the editorial is not clear. Thanks!! :) asked 12 Mar '17, 12:33

My approach is slightly different from what is described in the editorial, but I hope it will be easy to understand. If $a$ is our array of $n$ balls, let $f(i, j)$ be the cost of eliminating all the balls in $a[i..j]$. Our required solution is then $f(0, n1)$ (assuming 0based indexing). How do we calculate the value of $f(i, j)$? What about our base cases? Our final definition of $f$ is as follows $$f(i,j) = \begin{cases} 0 & \text{if } i=j+1, \\ 1 & \text{if } i=j, \\ f(i+1,j1) & \text{if } a[i]=a[j], \\ min\{f(i, k) + f(k+1, j) : i \le k \lt j\} & \text{otherwise}. \end{cases}$$ The dynamic programming solution will require $\mathcal{O}(n^2)$ space and $\mathcal{O}(n^3)$ time. Hope this helps! answered 13 Mar '17, 02:54
Nice explanation. Can you please present your views in regards of table filling DP? I mean how the approach given in editorial working?
(13 Mar '17, 08:23)
Thanks for the solution and it would be good if you can provide a table filling DP solution!
(13 Mar '17, 10:44)
1
In the editorial $f(i,j)$ is said to be for the range $i$ to $j$ inclusive, but the solution described is for $f(i,j)$ with $i$ inclusive and $j$ exclusive. There is another mistake in the editorial where "f(i1,k+1) + f(k+1, j)" should be "f(i+1,k) + f(k+1, j)". With these corrections I hope the explanation makes sense.
(13 Mar '17, 17:02)
I can easily interpret the mistake by looking through the solution. But i wanna know about how table is filling there?
(13 Mar '17, 19:10)
2
@bansal1232 by the editorial's approach it is clear that the cases must be filled in increasing order of $ji$, in other words the indices with $i$ close to $j$ must be filled first. Hence the solution fills in increasing order of the variable
(13 Mar '17, 23:17)
O..M..G!! Seriously meooow that's AWESOME!!!
(14 Mar '17, 11:38)
showing 5 of 6
show all

We have got 2 conditions 
So we wil try to form a recursive solution which we will later memoize.
2.we take a temp variable to store the ith color in array.
3.Take a variable ans= some large value because we want the minimum answer. 4.Now we need a loop to generate different index between i and j.
5.Now let's see different conditions in the loop. a. we check if(temp==ar[k]). b. if(k==i) i.e it is the first element (i.e ith element) so we call the function
c. if(k==j) i.e the last element 
since temp(which is 1 element was equal to ar[k] which means the first ball color(ith) is equal to last ball (jth) color ,so we don't have to pay for it and we just called the function from i+1 to k1. d. if both above case are not true this means k is in between i and j so it is simple to see that ans=min(ans,solve(i+1,k1)+solve(k+1,j)); leaving the first (ith) ball and kth ball we call the function. 6.Now we are left with the base cases We have 2 base cases because in last there are 2 conditions  a. 1 ball left i.e i==j.
b. otherwise if(i>j)
{
return 0; The memoization is simple which you can do by declaring a 2D array. First try it yourself and for reference you can see my code answered 13 Mar '17, 00:16
I appreciate your effort but try to explain in more simple and precise language, if u can.
(13 Mar '17, 00:22)
I agree with @bansal1232 .
(13 Mar '17, 01:03)

All right let me give a shot trying to explain you the solution. Let me first define a state. I am taking (i,j) as a state which means the given array from index i to j inclusively. n : size of array ( 0based array ) Aim : we need to find the solution for the state (0,n1) > whole array. How to accomplish it: we are going to collect answer for the desired state by taking the optimal combination of substates. Okay, once again get back to state (0,n1). Lets see the first element at index 0 i.e arr[0]. For first element we have two options either we will eliminate it individually (this will cost 1 move) or We will club it with some other index having same element as of arr[0]. lets say[ 0 , 1 , 2 , k1 , 4 , 5 , k2 , . . . , n1 ] are the indices of the array. and element at index 0 matches with element at index k1 and element at index k2 means arr[0] == arr[k1] == arr[k2]. Now once again get back to our answer for state concept. Let's assume we have answer for all possible states (i,j) except state(0,n1), which is the desired one. So,we can say ans(0,n1) = 1 + ans(1,n1) // means we are eliminating arr[0] individually Here, we have eliminated arr[0] individually so we add 1 to answer + we need to add answer for rest of array so we add the answer for the state (1,n1). or 0 1 2 k1 4 5 k2 .... n1   ans(0,n1) = ans(1,k11) + ans(k1+1,n1) This means we are clubbing idx 0 and k1 ( this counts 0 move ) ,but to do this we need to delete elements in between 0 and k1 , but as assumed we already the answer for that state(1,k11) + we also need to add the answer for array after k1 index because they are not eliminated so we will add answer for that state too i.e ans(k1+1,n1) or 0 1 2 k1 4 5 k2 .... n1   ans(0,n1) = ans(1,k21) + ans(k2+1,n1) Same above explaination. So, ans(0,n1) will be the minimum from above three conditions and hence, the question. We will just put the above relation for states in recursion by initializing the base states. Base States : ans(i,j) = 1 for all i == j ans(i,j) = 0 for all i > jMy Solution : here . answered 14 Mar '17, 06:11

brijwasi I recommend that you first check longest increasing subsequence algo in case you haven't read it yet. Try to take a small test case and formulate the dp table on paper. The author made 2 conditions, first one that it could increase the cost by 1 and delete the element, or he can match the element with some previous element (he checks with all previous occurances of that element) and stores it into a 2D matrix. That's what the editorial impresses upon me. Try constructing a dp table as the author says. Although at first you will feel that you're doing it mechanically or "just cause its told", you will realize the logic soon after that. I personally feel that yo should try doing it with pen and paper first, and if doubt persists, I will try my best to answer you. :) answered 13 Mar '17, 00:07

That Q is definitely not "Very Very Easy" lol.