# How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming? [duplicate]

I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by absolute differences.

Example:

Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups.
Let's say we want to minimize sum of absolute differences (SAD).
Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)
Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 <- That's what we want to minimize.

The question is how to solve it using dynamic programming?

The original question - https://stackoverflow.com/questions/9275280

• What have you tried so far? What happens when you have 1 number and $n > 1$ groups? What happens when you have 2 numbers and $n > 2$ groups? What happens when you have $n$ numbers and $n$ groups? What happens when you have $k$ numbers and $n = 1$ groups? Think about these, because these will be you base cases. If we have optimally solved this problem for $n-1$ groups, how can we use this information to solve it for $n$ groups? – ryan Apr 9 '19 at 19:56
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Apr 9 '19 at 21:19
• Nice question. It looks like none of the answers at the original question uses dynamic-programming. All of them are likely to run much slower than a proper solution by dynamic-programming when 𝑁 becomes larger. – John L. Apr 10 '19 at 1:20