Erase all the numbers ai where 1 < i < n, in some order, such that the total cost is minimized : <p>I encountered this problem.But I could not come up with any solution except brute force.Please suggest some efficient algorithm.
You are given a sequence of n numbers A = (a1, a2, ..., an). At one step, you can erase any number except for the leftmost and the rightmost ones. Erasing number ai costs ai−1 ∗ ai+1. Your goal is to erase all the numbers ai where 1 &lt; i &lt; n, in some order, such that the total cost is minimized. Give an algorithm to accomplish your goal, with O(n^3) time complexity.</p>
