Answering the question for if zeroes are not allowed:
We have the following system:
$\begin{cases} n_1+n_2+\dots+n_k=n\\
n_i\in \Bbb Z\\
n_i\geq 2\end{cases}$
By making a change of variable, setting $m_i=n_i-2$ we have the related system:
$\begin{cases}m_1+m_2+\dots+m_k=n-2k\\
m_i\in\Bbb Z\\
m_i\geq 0\end{cases}$
This is in a known form matching your previous question with answer $\binom{n-k-1}{k-1}$
Allowing $j$ zeroes to be used:
- pick which entries are zero
- apply the same process as above to the remaining entries
For specifically $j$ zeroes being used, without loss of generality, the first $j$ entries, we have the system $\begin{cases} n_{j+1}+n_{j+2}+\dots+n_k=n\\
n_i\in\Bbb Z\\
n_i\geq 2\end{cases}$
Making a change of variable, $\begin{cases} m_{j+1}+m_{j+2}+\dots+m_k=n-2(k-j)\\
m_i\in \Bbb Z\\
m_i\geq 0\end{cases}$
This is in a known form with $\binom{n-2(k-j)+(k-j)-1}{k-j-1}=\binom{n-k+j-1}{k-j-1}$
The total then is:
$$\sum\limits_{j=0}^{k−1} \binom{k}{j}\binom{n-k+j-1}{k-j-1} = \sum\limits_{j\ge k−\frac{n}{2}}^{k−1} \binom{k}{j}\binom{n-k+j-1}{k-j-1}$$
What you're looking for is called the $2$-Wasserstein distance between your sets of points.
The Hungarian method (also named (Khun-)Munkres, depending on the paper) has long been used to solve this exactly, but auction methods converge really fast.
Moreover, in $\mathbb R^d$ with low dimension, you can even use kd-tree methods to make local requests and accelerate the computation. You can see this in a paper (here the sets of points $A$ and $B$ are in a space a little more complicated than $\mathbb R^2$, but you could forget about that and the paper is quite clear). The complexity is hard to estimate because it depends on the heuristic on which the auction method is based, but the paper regress their method's speed to $O(n^{1.6})$. In dimension $d > 2$ it might be a little less efficient but it's better than $O(n^3)$ anyway.
Best Answer
First, show that if the list $(n_1, \dots ,n_m)$ has two entries $n_i$ and $n_j$ for which $$ \ell>n_i\ge n_j>0, $$ then the list is not minimal. Proving this intermediate inequality is helpful: $$ \sqrt{n_i+1}+\sqrt{n_j-1}< \sqrt n_i +\sqrt{n_j}. $$ This shows that the list obtained by replacing $n_i$ with $n_i+1$ and $n_j$ with $n_j-1$ has a smaller sum of square roots. Therefore, an optimal list can have at most one entry which is neither $0$ nor $\ell$. Let us call this entry $q$. If we let $k$ be the number of occurrences of $\ell$, we have $n=k\ell+q$, as required.