Example
Consider the following game. You are given a sequence of $n$ positive numbers $(a_1, a_2, …, a_n)$. Initially, they are all colored black. At each move, you choose a black number $a_k$ and color it and its immediate neighbors (if any) red (the immediate neighbors are the elements $a_{k-1}$, $a_{k+1}$ ). You get $a_k$ points for this move. The game ends when all numbers are colored red. The goal is to get as many points as possible.
Describe and analyze an efficient dynamic programming algorithm for this problem that runs in O(n) and returns optimal solutions.
Solution
First, we want an array where the $i^{th}$ position stores the value of the optimal solution for subproblem consisting of the first $i$ numbers of the sequence. It is obvious when $i=1$, we have no other choice than choose $i$. For $i=2$, we can choose one or the other. For $i=3$, we can either choose the third number which eliminates the second, or we can choose the second which eliminates both the first and the third.
Now, let’s look at the $i^{th}$ number, still, we have two choices. If we pick the $i^{th}$ number, then it eliminates the $(i-1)^{th}$ number and we need to look at the $(i-2)^{th}$ number. The other choice is that we do not pick the $i^{th}$ number and we use the $(i-1)^{th}$ number instead. So the recursion will be:
Retracing for the solution can simply invert the recursive formula to see which of the two gave the observed value. Both filling the table and retracing steps takes linear time, so the time we need is $O(n)$.