undefined

Suppose that you are trying to stack boxes in a corridor that is 10 feet high. The boxes can all stack on top of each other, but they must be stacked in the same order as they start in. Each stack of boxes will probably have space left over between the top of the stack and the ceiling. For example, if you have boxes of heights 6, 3, 2,9 then you could have the first stack with the 6 foot and the 3 foot box, the second with just the 2 foot box, and the third with just the 9 foot box. The square metric of space left over in this case would be 12 +82 +12. That is, you compute the amount of space left by each stack, square it, and add the results together. (a) Find a way to stack the boxes in the example that results in a lower square metric. (b) Given a sequence of box heights 21, 22, ..., An, find a dynamic pro- gramming solution to the problem of computing the minimal possible square metric for stacking the boxes. (c) Analyze the running time of your solution