An DP algorithm problem

You have a sequence of n sticks, where the i-th stick has integer length li . You need to lay out these sticks horizontally, and in sequence, in rows of integer width M such that the sum of the squares of the wasted space in the occupied rows is minimized. You can assume that each li M. In other words, suppose you assemble the first k1 sticks in sequence in the first row, then sticks k1+1 though k2 in row 2 , and so on until all sticks are placed within r rows. Then, row i will have sticks ki1+1,,ki in that order, and the occupied length of row i is oi=j=ki1+1ilj. We need OiM for each row i in order for the solution to feasible, and the cost of this feasible solution is C=i=1r(Moi)2 You need to design a dynamic programming algorithm to compute the cost of an optimal solution. Be sure to establish an optimal substructure result for an optimal solution, de termine a recursive expression for the cost of an optimal solution, and give an efficient algorithm to compute the cost of an optimal solution. You do not need to give an algorithm that outputs an actual solution, so you only need to present Steps 1-3 for a DP solution. For full credit it suffices to give a correct DP algorithms that takes time and space O(n2). We provide a simple example with 3 sticks and M=4