Minimal steps to reach a natural number by a signed arithmetic progression $F:=\big\{f\,\big|\,\text{function }f: \mathbf N\rightarrow \{1,2\}\big\}$.
\begin{align}
&\min_{f\in F,\,k\in\mathbf N} k, \\
&\sum_{i=1}^k (-1)^{f(i)}i = n \in\mathbf N.
\end{align}

*

*Is there an analytical or an asymptotic solution to this problem for general $n$?


*For a specifically given $n$, what would a good algorithms to solve this problem? The dynamic programming?
 A: Essentially, for any given $n$, the task is to select $+$'s and $-$'s to reach $n$ as fast as possible (minimize $k$):
$$\pm 1 \pm 2 \pm 3 \pm \dots \pm k = n$$
If we don't worry about overshooting $n$, the obvious strategy is to only add and never subtract. If $n$ is a triangular number, this will give us the answer. This would necessarily be the optimal solution since we did not subtract at all.
If $n$ is not a triangular number, at some point $k'$, we will overshoot $n$:
$$1 + 2 + 3 + \dots + k' > n$$
Since we need $k$ at least $k'$ to even reach $n$, we know that $k=k'$ is optimal if it works.
Consider the value $1 + 2 + 3 + \dots + k' - n$. We will denote this amount as $a$. We know that $a < k'$. If $a$ is even, then we can switch the operator of $a/2$ to $-$, and we have our optimal solution.
Figuring out the solution for when $a$ is odd may be trickier.
EDIT:
Figured out the "odd" case!
If $a$ is odd, then we cannot have $k = k'$ because there is no expression that will give us exactly $n$ using $k'$ terms. For any signs we switch in the $k'$ terms, the total sum will retain the same parity, so we cannot reach exactly $n$. Thus, if we can find a solution with $k'+1$ terms, it is necessarily optimal.
Consider $1 + 2 + 3 + \dots + k' + (k'+1) = n + a + k'+1$.
If $k'$ is even, then consider the value $\frac{a+k'+1}{2}$. We have
$$\frac{a+k'+1}{2} < \frac{2k'+1}{2} = k' + 1/2 \,.$$
So, $\frac{a+k'+1}{2} \leq k'$. Thus, it is in our series, so we can assign it the operator $-$, and we have achieved exactly a sum of exactly $n$.
Now, to consider what happens when both $a$ and $k'$ are odd...
EDIT 2:
First off, is it possible to find a solution with $k=k'+1$ when $k'$ is odd?
Well if we use all $+$'s, we have $1 + 2 + 3 + \dots + k' + (k'+1) = n + a + k' + 1$. As before, switching the signs of any of our terms will preserve the parity of the total sum. Since $a$ and $k'$ are odd, $n+a+k'+1$ has opposite parity from $n$. So, no rearrangement of signs will enable a series of $k'+1$ terms to work.
Our next candidate is $k=k'+2$. Let us consider the following sum:
$$1 + 2 + 3 + \dots + k' + (k'+1) + (k'+2) = n + a + (k'+1) + (k'+2)$$
We are too high by the quantity $a + 2k' + 3$. We can switch the sign of $k'$ and switch the sign of $\frac{a+3}{2}$, and we arrive at exactly $n$ with $k=k'+2$.
And that concludes the proof! No dynamic programming needed - a purely analytic solution.

TL;DR
Let $k'$ be the least integer such that $T_{k'} \geq n$. If $T_{k'}$ and $n$ have the same parity, then $k=k'$. Else, $k$ is equal to the least odd integer greater than $k'$.
See this OEIS sequence.
A: Continuing on @inavda's answer, for a given $n$ we find the minimum number of terms, which is the index of the smallest triangular number not smaller than $n$, and with the same parity. As the parities of the triangular numbers follow the pattern $e,o,o,e,e,o,o,e,e,\cdots$, we can find the smallest triangular number not smaller than $n$, and increment once or twice as needed to reach the desired parity.
Then we repeat this operation recursively on the half of the residue $\dfrac{k(k+1)}2-n$ to obtain the desired correction.
Example: $n=37$
$$37\le T_9=45, \text{half residue }4\to+++++++++$$
$$4\le T_3=6, \text{half residue }1\to---+++++$$
$$1=T_1\to+--++++++$$

The smallest triangular number is obtained by
$$\frac{k(k+1)}2\ge n$$ or
$$k\ge\frac{\sqrt{8n+1}-1}2,$$
$$k=\left\lceil\frac{\sqrt{8n+1}-1}2\right\rceil.$$

Notice that the procedure fails for $n=2$, as the smallest triangular number is $T_3=6$ and the half residue is again $2$. Also for $n=5$, $T_5=5$ and the half residue is $5$. These are the only fixed points. We solve these with $2=1-2+3$ and $5=1-2-3+4+5$.

Notice that the residue is on the order $O(\sqrt n)$, so that the successive residues decrease very quickly, and the recursion depth is of order $O(\log\log n)$.

Update:
Checking the example, it turns out that this procedure is wrong.
