Suppose we have a sequence of n objects a₁, a₂, , a_n where each a_i has size s_i . We wish to store these objects in buckets such that the objects in each bucket are consecutive members of the sequence. Assume that we have buckets of k different sizes l₁, , l_k such that n buckets are available for each size. The cost of any bucket is proportional to its size. The objects a_j+1, a_j+2, , a_j+s fit into a bucket of size l_r if and only if X _j+s i=j+1 s_i l_r. The problem is to store the objects in buckets with the minimum total cost such that only consecutive objects can be stored in the same bucket. For example, it is not allowed to store objects a_i and a_i+2 in the same bucket while object a_i+1 in a different bucket.

Describe an algorithm that can solve this problem in O(n ² ) time by formulating the problem as a shortest path problem.

Do present an algorithm that works in O(n ^k ) time for a constant k > 2.