My problem is as follows: Given n points on a line segment and a threshold k, pick the points on the line so that would minimize the average difference of the distance between each consecutive point and the threshold.
For example: If we were given an array of points n = [0, 2, 5, 6, 8, 9], k = 3
Output: [0, 2, 6, 9]
Explanation: when we choose this path, the difference from the threshold in each interval is [1, 1, 0] which gets an average of .66 difference. If I chose [0, 2, 5, 8, 9], the differences would be [1, 0, 0, 2], which averages to .75.
I understand enough dynamic programming to consider several solutions including memorization and depth-first search, but I was hoping someone could offer a specific algorithm with the best efficiency.