# findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $$x_{1}$$, $$x_{2}$$, . . . , $$x_{n}$$} where $$x_{i} \in Z$$ . and a K and it is $$Z^{+}$$ . The goal is to ﬁnd k intervals $$I_{1}, I_{2}, . . . , I_{k}$$ so that each $$x_{i}$$ is in one of the intervals $$I_{j}$$ and so that the sum of the squared lengths of the intervals $$I_{k}$$ is as small as possible. For instance, S = {1, 3, 6} and K = 2, the best outcome is $$I_{1}$$ = [1, 3], $$I_{2}$$ = [6, 6], and the sum of squares of the lengths is 4.

We can approach our algorithm as: First of all, we sort S and let S = { $$x_{1}$$, $$x_{2}$$, . . . , $$x_{n}$$} where $$x_{1}$$<$$x_{2}$$<, . . . , <$$x_{n}$$. Then we can use dynamic programming. We let L[i, m] be the shortest sum of squared lengths of m intervals that cover all of $$x_{1}$$, . . . , $$x_{i}$$. Notice that L[1, m] = 0 for all 1 ≤ m ≤ k and L[i, 1] = ($$x_{i}$$$$x_{1})^2$$ for 1 ≤ i ≤ n. If we have a cover of $$x_{1}$$, . . . , $$x_{i}$$, suppose the interval that covers $$x_{i}$$ also covers all points $$x_{j}$$ , $$x_{j+1}$$, . . . , $$x_{i}$$. Then, the sum of the squared lengths is at least ($$x_{i}$$$$x_{j}$$ $$)^2$$ + L[i − 1, m − 1]. Therefore, the minimum such value is actually obtainable.

How can we know for sure "that L[1, m] = 0 for all 1 ≤ m ≤ k and L[i, 1] = $$(x_{i} − x_{1})^2$$ for 1 ≤ i ≤ n" and ?

Seem like we need to have a 2D-array? How can I visualize this solution better?

Here is what draw: How can we fill the 2D array with ($$x_{i}$$$$x_{j}$$ $$)^2$$ + L[i − 1, m − 1] ?

• Please credit the original source of this exercise and of all copied text/material. Thank you! – D.W. Jan 30 '19 at 18:55
• We'd prefer that you ask only one question per post. I see three different questions here. – D.W. Jan 30 '19 at 18:56