Billboards - Interviewstreet Problem

This is my first post of possibly a series about my attempts to solve some of the Interview Street Problems. Am a beginner and hence its going to take a lot of learning to solve some of these problems.

Its evident that the right solution is not that solves the problem but the one that solves it efficiently ! ;) Well tht aint easy. 

For this particular problem one of the approach suggested was to use Dynamic Programming. Heres a really gud tutorial for an intro on wht that is . 

http://www.youtube.com/watch?v=6h6Fi6AQiRM 

For this particular problem tho, tht algo has to be tweaked. 

The base algo that I used is this, 

n,k are no. of positions and k is the grouping limit.

K(j,i){

if(j==n)

  return 0;

else

     if(i==k)

        return Knapsack(j+1,0)  // which means ignore the current position cause a blank space is madatory

     else

        return max( Knapsack(j+1,i) , v[j] + Knapsack(j+1,i+1))  // case where current elem is chosen and case where its not 

}

Well thts the Base Algorithm. Using this algo as such solves 4/10 cases.. Jump of 1000 Rank (Worth it !!) 

Now am looking for a efficient optimization of this algo to reduce the running cause the rest of the testcases give a time limit exceeded error ( Inefficient Algo used )  .  Any help would be appreciated btw :)


Made some progress on this one. Implemented Dynamic programming iterative way which solved 7 of the 10 cases. Way too easy than my previous approach.

Took reference from this post in stackoverflow http://stackoverflow.com/questions/9376976/removal-of-billboards-from-given-ones .

Made an optimization to use only two rows and re use it instead of assigning memory for n rows. Efficient usage of memory which avoid Core Dump Problem. (Idea from a post in Topcoder) . Now 3 testcases give me a time limit exceeded error. Will work on them now.