3

I'm trying to solve this topcoder problem. I have read the solution analysis but still cannot understand.

The basic idea of the solution is to think backwards and insert element instead of deleting. But how can this reduce the complexity of the problem ?

I do understand that this is a dynamic programming problem. I read on the wikipedia that DP problem avoid solving sub problems repeatly and thus reducing the complexity. But I do not see any sub problem redundency here.

Thanks

Problem Statement The Casket of Star (sic) is a device in the Touhou universe. Its purpose is to generate energy rapidly. Initially it contains n stars in a row. The stars are labeled 0 through n-1 from the left to the right. You are given a int[] weight, where weight[i] is the weight of star i.

The following operation can be repeatedly used to generate energy:

Choose a star x other than the very first star and the very last star.
The x-th star disappears.
This generates weight[x-1] * weight[x+1] units of energy.
We decrease n and relabel the stars 0 through n-1 from the left to the right.

Your task is to use the device to generate as many units of energy as possible. Return the largest possible total amount of generated energy.

Improve this question
2
  • 1
    Think about n = 3. Then think about n = 4, remembering what you've already thought about. Then think about n = 5, remembering what you've already thought about. Then think about all the things you've thought about so far. Commented Mar 2, 2012 at 9:22
  • OK I can see why there's repeated computations: if we have 3 5 6 7 8 9 2and pick 5, then we have 3 6 7 8 9 2; if we pick 6, then we have 3 5 7 8 9 2; in both case, the sub sequence 7 8 9 2 gets computed . Commented Mar 2, 2012 at 10:03

1 Answer 1

Reset to default
3

The sub-problem f(start,end) is to work out the most energy that can be got from deleting all the interior stars in the range [start,end]. (An interior star is any star except for the endpoints.)

There are n stars so there are about n*n/2 of these sub-problems.

The original problem is the answer to the sub problem with start=0 and end=n-1.

The sub-problems can be solved by considering all choices for the last node to be deleted. For each choice x we add the cost f(start,x) of deleting stars before x, and the cost f(x,end) of deleting stars after x, and the cost weight[start]*weight[end] of deleting x itself.

This takes O(end-start) operations so the entire problem can be solved in O(n^3)

Improve this answer
2
  • Hi peter, how do you calculate f(start,x) and f(x,end)? by recursive methode ? Commented Mar 2, 2012 at 22:45
  • Recursive would certainly work. (Make sure that you save the results of calculating a sub-problem or you will repeat a lot of calculations.) Alternatively, you can avoid the function call overhead by iterating over the length (start-end) of the subproblem, and iterating over the start point, and saving the results in an array. Commented Mar 3, 2012 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.