We want to demolish and move a bridge from one location to another.
The bridge is made out of $m$ road segments all connected $[0,1]$, $[1,2]$, $[2,3]$...$[m-1,m]$
We have a given function $f$ which describes the cost of moving $j$ connected road segments, for example, say we want to move the segment $[1,3]$ then the cost would be $f(2)$ since it's $2$ road segments. if we want to move $[3,4]$ it will cost $f(1)$.
We also know that splitting a bridge costs $k$. Example, if at first we had the segment $[0,5]$ we can split it by hitting spot $4$ with a hammer to get the segments $[0,4]$ and $[4,5]$. Each such split costs $k$.
Let $c(n)$ be the minimal cost for demolishing and moving a bridge of $n$ segments.
Find a recursive formula that describes $c(n)$.
What I did:
Here is my logic, hope it is sound.
if $n=1$ then we don't have a choice, we cant split it or play around with it, we just need to move it to the new location, it will cost $f(1)$. So $c(1)=f(1)$.
Now suppose $n$ is some unknown number larger than one. Now we have a few options:
1) We could move it as one piece, it will cost $f(n)$.
2) We could break it at point $n-1$, that way we will have the segment $[n-1,n]$ and $[0,n-1]$. The cost of breaking at one point is $k$, the cost of moving $[n-1,n]$ is $f(1)$ and the cost of moving $[0,n-1]$ is $c(n-1)$, that is the lowest price. so overall, if we break at $n-1$, the cost is $c(n)=k+f(1)+c(n-1)$.
3) We could break the bridge at point $n-2$ to get the segments $[n-2,n]$ and $[0,n-2]$. As before, the cost would be $c(n)=k+f(2)+c(n-2)$
And so on, generally, if we break at point $n-i$ the cost would be $c(n)=k+f(i)+c(n-i)$.
Since we are looking at the best case, where the cost is minimal, I reached the conclusion that the minimal price would be represented by the formula $c(n)=\min_{1\leq i < n}(k+f(i)+c(n-i)),f(n)$
It's either the minimal value of $k+f(i)+c(n-i)$, or $f(n)$. whichever is lower.
Your recurrence is correct. You can reduce the number of terms to be examined, however, by observing that if you cut the bridge at all, there is always a cut at most $\lfloor n/2\rfloor$ from one end, so that any of the following recurrences can also be used:
$$\begin{align*} c(n)&=\min\left\{f(n),\min_{1\le \ell\le\lfloor n/2\rfloor}\big(k+c(\ell)+c(n-\ell)\big)\right\}\\ &=\min\left\{f(n),\min_{1\le \ell\le\lfloor n/2\rfloor}\big(k+f(\ell)+c(n-\ell)\big)\right\}\\ &=\min\left\{f(n),\min_{1\le \ell\le\lfloor n/2\rfloor}\big(k+c(\ell)+f(n-\ell)\big)\right\} \end{align*}$$