# Minimum moves to “stabilize” an array

We have given an array of size $$N$$, consisting of positive integers, and an integer $$H$$. We also know that an array is stable iff $$|A_i - A_{i-1}| \leq H$$ for each $$1. We can modify the element by adding +1 to some element or by adding -1 to some element, we don't have a limit on how much we can use those operations, but we want to make the array stable in minimum moves.

I started solving the task by writing a dynamic programming relation, described by the state $$f(i, j)$$ meaning the minimum moves to stabilize the first $$i$$ elements of the array, such that the last element is equal to $$j$$.

However it seems that this method is slow for big values of $$N$$. How would you approach solving this problem?

Let $$M=\max_i|A_i|$$.
Besides the linear programming method proposed in this post (which is suitable for small $$N$$ and large $$M,H$$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $$f(i-1,j-H),\ldots,f(i-1,j+H)$$.
Let $$f(i,j,k)$$ be the minimum moves to stabilize the first $$i$$ elements of the array, such that the last element is in the range $$\left[j,j+2^k\right)$$. Then we have $$f(0,j,0)=0$$, $$f(i,j,0)=|A_i-j|+ \min\left\{f\left(i-1,j-H,\hat{k}\right),f\left(i-1,j+H+1-2^{\hat{k}},\hat{k}\right)\right\}$$ where $$2^{\hat{k}}>H$$, and $$f(i,j,k)= \min\left\{f(i,j,k-1),f\left(i,j+2^{k-1},k-1\right)\right\}$$ for $$k>0$$. Note each entry can be calculated in $$O(1)$$ time if we calculate them in some proper order.
Note in an optimal solution, the final $$A_N$$ must be in the range $$[-(M+NH),M+NH]$$ (otherwise the final elements are all either greater than $$M$$ or less than $$-M$$, which is not optimal), so we need to calculate $$f(i,j,k)$$ for all $$i,j,k$$ such that $$0\le i\le N$$, $$j\ge -(M+(2N-i)H)$$, $$k\ge0$$ and $$j+2^k\le M+(2N-i)H+1$$. The time complexity is $$O\left(N(M+NH)\log (M+NH)\right)$$, while the naive $$f(i,j)$$ solution takes $$O(N(M+NH)H)$$ time.
You can further use the range minimum query technique to reduce the time complexity to $$O(N(M+NH))$$.