i have been stuck in spoj problem ACTIV. Due to constraints it is getting difficult to solve for me.Kindly someone provide some hint so that i can proceed
thanks in advance
hmm actually you have recurrance relation that
F(Pos) = F(pos + 1);
F(pos) = F(pos) + F(Next(pos));
here Next(pos) represent that when we take pos’th element or activity then we skip those elements which can’t be participate in this set
So This part and Base condition is easy
i think this is enough
IF you want to know more do pratice
Problem link : SPOJ ACTIV
I have written a recursive solution for this problem and it is working fine.But i am not able to store the calculated result due to memory constraint…So i want to Know how to further Minimize the state space of function arguments.
My solution link : Here in order to memoize i need 2 D array…Can any body help me to improve this recursion so that i need only 1D array.Actually at present I am comfortable little bit in top down approach.