dynamic programming - Algorithm puzzle: minimum cost for allow all persons standing on a line to communicate with each other -

i have algorithm design puzzle not solve.

the puzzle formulated this: there n persons standing on number line, each of them maybe standing on integer number on line. multiple persons may stand on same number. 2 persons able communicate each other, distance between them should less k. goal move them each pair of 2 persons can communicate each other (possibly via other people). in other words, need move them distance between neighboring 2 persons smaller k.

question: minimum number of total moves? feels falls greedy algorithm family or dynamic programming. hints appreciated!

we can following in o(n):

calculate cost of moving people right of person i towards person i @ acceptable distance:

costright(a[i]) = costright(a[i+1]) + (a[i+1] - a[i] - k + 1) * count of people right  k = 3;  = { 0,  3, 11, 17, 21} costright = {32, 28, 10,  2,  0} 

calculate cost of moving people left of person i towards person i @ acceptable distance:

costleft(a[i]) = costleft(a[i-1]) + (a[i] - a[i-1] - k + 1) * count of people left  k = 3;  = { 0,  3, 11, 17, 21} costleft  = { 0,  1, 13, 25, 33} costright = {32, 28, 10,  2,  0} 

now have cost both directions can in o(n):

mincost = min(costright + costleft) a[i] mincost = min(32 + 0, 28 + 1, 13 + 10, 25 + 2, 33 + 0) = 23 

but that's no enough:

k = 3;  = { 0,  0,  1,  8,  8}        carry:     -2  -4       3 costleft  = { 0,  0,  0, 11, 11}        carry: -3   5      -2 costright = { 8,  8,  8,  0,  0} 

the optimum neither 11 nor 8. test current best moving towards greatest saving:

move 1 2, cost = 1  k = 3;  = { 0,  0,  2,  8,  8}        carry:     -2  -2     -10 costleft  = { 0,  0,  0, 10, 10}        carry: -2          -2 costright = { 6,  6,  6,  0,  0}  mincost = 1 + min(0 + 6, 0 + 6, 0 + 6, 10 + 0, 10 + 0) = 1 + 6 = 7 

not quite sure how formularize efficiently.