Efficient algorithm for this optimization problem? Dynamic programming?
This is just an extension to @Sébastien Loisel's answer.

Notice minimize $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$ is equivalent to minimize $(x_i-(y_i-c_i))^2$ subject to $x_i\geq x_{i-1}$. Let $a_i=y_i-c_i$, then this is precisely the isotonic regression problem. There exist a $O(n)$ time algorithm.