I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not homework: i've already a solution, just considering if i'm ok with the theory.
Suppose we want to replicate a file over a collection of $n$ servers $S_1, S_2 , \ldots , S_n$. Each server $S_i$ has a placement cost $c_i$ to place a copy of the file at $S_i$. If a user requests the file from $S_i$ and no copy is present, then servers $S_{i+1}, S_{i+2}, S_{i+3}, \ldots$ are searched in order until a copy is found, say at $S_j$ (where $j > i$). This results in an access cost $a_i$, where $$ a_i= \begin{cases} j-i \qquad \hbox{if $S_i$ does not contain a copy the file} \\ 0 \qquad \hbox{ if $S_i$ contains a copy of the file} \end{cases} $$ We require that $S_n$ contains the file, so that all searches will terminate. Given $I \subset \left\{1,\ldots, n − 1\right\}$, a subset of servers to place the file on, we define the total cost
$$ c(I) = c_n + \sum_{i \in I} c_i + \sum_{i=1}^{n} a_i $$
To be the sum of the placement costs for each server that contains the file (recall that $S_n$ must contain the file), plus the sum of the access costs associated with all $n$ servers. Design a polynomial-time algorithm to compute a subset I of servers to contain the file that minimizes total cost.
My approach is to consider every possible choice, like for other problems e.g. segmented least squares, ending up with a $O(n^4)$ running time algorithm.
Anyway it looks like there is a better solution, given by the following recurrence:
$$ OPT(j) = c_j + \displaystyle\min_{0 \leq i < j}(OPT(i)+\binom{j-i}{2}) $$
With the initialitazions $OPT(0)= 0$ and $\binom{1}{2}=0$. The answer is given as usual by $OPT(n)$. This is to me very counterintuitive: why the binomial coefficient, and why the number $2$?.
Is it a standard way to approach similar problems?