algorithms – Proving existence of an optimal substructure for the DP problem “Equal” from HackerRank

Let $langle o_1, o_2, o_{m+1}rangle$ be a non-empty optimal sequence of operations that distributes the chocolates evenly, i.e., such that the final distribution is $(k,k,k, dots, k)$.

Let $alpha_i$ be the number of candies given to the $i$-th person by operation $o_{m+1}$ and consider the subsequence of operations $langle o_1, o_2, dots, o_mrangle$. We need to show that $langle o_1, o_2, dots, o_mrangle$ is an optimal sequence of operations to obtain the final distribution $(k-alpha_1, k-alpha_2, dots, k-alpha_n)$.

The proof is by contradiction. Suppose that $langle o_1, o_2, dots, o_mrangle$ is not optimal, hence there is some sequence of operations $langle o’_1, o’_2, dots, o’_ell rangle$ that yields the final distribution $(k-alpha_1, k-alpha_2, dots, k-alpha_n)$ and such that $ell < m$.
Therefore, the sequence $langle o’_1, o’_2, dots, o’_ell, o’_{m+1} rangle$ yields the distribution $((k-alpha_1) + alpha_1, (k-alpha_2) + alpha_2, dots, (k-alpha_n) + alpha_n) = (k, k, dots, k)$.
The number of operations of the above sequence is $ell + 1$ and, by the optimality of $langle o_1, o_2, dots, o_{m+1}rangle$, we know that $ell+1 ge m+1$ since every sequence that yields $(k,k,dots,k)$ must consist of at least $m+1$ operations.
This results in the contradiction $m+1 le ell+1 < m+1$.