Finding a partition with minimum "maximal length"
This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:


   How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question. 


This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are the subproblems stated explicitly.


   Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$?
 $$ m(w,k) := \min_{i_0 = 0,\,i_k = w,\,i_1\lt\cdots&lt;i_k} \max\{x_{i_1} - x_{i_0},\,x_{i_2}-x_{i_1},\,\cdots,\,x_{i_k} - x_{i_{k-1}}\} $$
 What is the technique? We replace the last item $1-x_{i_n}$ with $x_k - x_{i_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'&lt;w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x_{n^2+1} = 1$.