MY first DP Problem
I solved my first problem on dp on spoj .Here is the link to the problem.
I could clearly observe that there were subproblems which were overlapping!! . So indeed a dp solution would work!!. I could understand that the previous optimal states helped to solve the higher level states.
It was almost an hour I was not able to formulate the recursion!!! However on close examination!! I could write the recursive procedure but still I was not satisfied as I came up with the solution based on observation.
I went to Pranjal's room!! He explained to me the procedure and also helped me identify states and the way the function could be formulated. He also told me that there were states which were redundant but there is no harm if we use them!!!
I had somewhat a clear picture of how the states varies and the way recursion should be written!!
I solved it in four different ways each time defining the function to be reprsenting the optimal solution diffrently!!! I tried out the bottom-up and top-down and recursive procedure as well.!
Friends are family you choose
I tend to have very few friends and It been a year and a half in BIT. I have just 2 friends Abhishek(Taker) && Pranjal . But I am extremely happy and contended!! As the size of the friend circle doesn't matter!!! what matters is the bond you share and the people you hang out with!!!