# Determining the optimal cost through dynamic programming.

There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k$ is $f (j, k)$. One cable can serve a maximum of 10 houses. The optimal cost of serving houses $\{i, i+1, i+2, \dots, n\}$ is $V_i$. Write down $V_i$ in terms of $V_{i+1}$ such that it can be evaluated.

The expression that I obtained is $$V_i=\text {Min}\{f (i, i)+V_{i+1}, f (i, i+1)+V_{i+2}, \dots, f (i, i+9)+V_{i+10}\}$$

Is it correct? I'm not so sure it leads to a simplification completely in terms of $V_{i+1}$ though.

• @Cristopher- Why do you think I misread it? – fierydemon Jun 20 '15 at 3:11