The problem of clustering a sorted sequence of one$-$dimensional points x$1,...,$ xn entails splitting the points into k clusters $($where k $<=$ n is an input parameter$)$ such that the sum of the squared distances from each point to its cluster mean is minimized. Give a dynamic programming algorithm that takes as input an array x$[1..$n$]$ and a positive integer k$,$ and returns the lowest cost of any possible clustering with k or fewer clusters. $($a$)$ Define the subproblem that you will use to solve this problem precisely, and give a recurrence relation that

will help you solve this problem. Formally prove the correctness of the recurrence relation.

$($b$)$ Describe an algorithm that solves this problem based on your answer to $($a$),$ and show that your algorithm

achieves the desired running time