Given an 0-index-based array. You have to make the array non-increasing or non-decreasing. The operation you can use:
- Choose an index $$$0\leq i<n$$$.
- Make $$$array[i] = array[i]-1$$$ or $$$array[i] = array[i]+1$$$.
Find the minimum operations required to achieve the target.
- $$$Array.size()\leq1000$$$
- $$$0\leq Array[i] \leq1000$$$
Sample: $$$array = [3,2,4,5,0]$$$
$$$ans = 4$$$
final $$$array = [3,3,3,3,0]$$$
Please help me understand how to reach an optimal solution.
Check this out https://codeforces.me/problemset/problem/13/C
For the non-ascending part, consider a[i] := 1000 — a[i] then do the non-descending algorithm on new a[] and take optimal solution from the two
Let $$$dp(i,j)$$$ for $$$i \in [0,n-1]$$$ and $$$j \in [0,max]$$$ (max = 1000) be the minimum number of steps to make $$$a_i, a_{i+1}, \ldots, a_n$$$ increasing with $$$a_i = j.$$$ Do a similar dp for decreasing sequences.
Then we have $$$dp(i, j) = |a_i - j| + \min_{j \leq k \leq max} \{ dp(i+1,k) + |a_{i+1} - k| \} = |a_i - j| + f(i+1,j).$$$
Naively computing this is $$$O(n \cdot max^2),$$$ but we can note that for a given $$$i,$$$ we can compute all the values $$$f(i+1,j)$$$ for $$$j=max,\ldots,1$$$ in $$$O(max)$$$ since $$$f(i+1,j) = \min( dp(i+1,j) + |a_{i+1} - j|, f(i+1,j+1) ).$$$ Thus we can compute $$$dp(i,j)$$$ for all $$$j=1,\ldots,max$$$ in $$$O(max)$$$ and so the overall runtime is $$$O(n \cdot max).$$$