The challenge is as follows: http://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416
Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].
Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:
If there are no more pancakes remaining, terminate. Choose a pancake uniformly at random from the pancakes that have not been chosen yet. If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it. Place the chosen pancake on top of the stack and go back to step 1. You are given the int[] d with N elements. The total deliciousness of a serving of pancakes is the sum of the deliciousness of all pancakes used in the serving. Compute and return the expected value of the total deliciousness of the pancakes chosen by Charlie.
This problem involves probability and i dont get the DP solution for it.