Dynamic programming: Maximize total value I was trying to solve this problem using dynamic programming.
We have $n$ objects in a row where each object has a value represented with a positive number.
This is encoded with an array $V[1], . . . , V[n]$ where $V [1]$ is the value of the first object in the row,
$V [2]$ is the value of the second object in the row and so on. We want to select a set $I \subseteq \{1, . . . , n\}$
of objects in such a way that the sum of its values, $\sum\limits_{i\in I} V [i]$, is as large as possible. However,
we cannot select objects that occupy consecutive positions in the row. That is, if we select object
$i$, then we cannot select object $i − 1$ nor object $i + 1$. For example, if $V = (6, 4, 3, 7, 3)$ then the
best option would be to select the first object (with value $6$) and the fourth object (with value
$7$). It is easy to see that any other option would have smaller total value.
We want a dynamic programming algorithm that, given as input array $V$ , computes the value
of the set with highest value. Note that, in order to simplify matters, we do not ask that the
algorithm returns the set, only its total value.
The probleem comes when it says &quot;we cannot select object $i − 1$ nor object $ i + 1$&quot;. For $i-1$, the recursive case should be Optimal$(j-2)$+Value$(j)$, but no idea about $i+1$.
For $k \in [\![1, n]\!]$, you can define $f(k)$ as the maximum value reachable using objects $1$, $2$, …, $k$, without two consecutives objects.
Now the key to the dynamic programming implementation is to see that:
$\forall k \in [\![3, n]\!], f(k) = \max(f(k-1), f(k-2) + V[k])$
The reason is that to compute $f(k)$, you can either keep the $k$-th object or not. If you keep it, then you cannot keep the $k-1$-th object.
Finally, you want to compute $f(n)$.