For the following I did not check in depth the rules related to end-of-period/beginning of period, so this is something you should carefully check for your problem. However, the approach does not differ much if this is incorrect (but your numbers may end up different). Sanity checks are definitely in order before you take this answer for granted!
I think your state variable is a bit strange. Given the problem, I would be inclined to define $p_{i,j}$ as the cumulative profit in years periods from $1$ up to and including period $i$, assuming there is currently a machine with age $j$ in time period $i$.
We first need to define recurrent relationships on the state variables $p_{i,j}$. For the first period, where $i=1$, we can do so as follows:
$$
p_{1,j} = \left\{ \begin{array}{ll} 5 & \mbox{ if } j=2 \\
-\infty & \mbox{ otherwise }
\end{array}\right.
$$
The idea here is that we have a profit of $5$ (thousand) for the state where we have a two year old machine at the end of the first year.
Since it is not possible to have any other machine at the end of the first year, the states related to that situation have
$-\infty$ profit, as this value will be discarded by the consecutive steps of the recurrence relation.
For the later periods, where $i \geq 2$, we can compute the best possible profit based on the previous period by means of the following
recurrence relation
$$
p_{i,j} = \left\{ \begin{array}{ll}
\max_{k \in \{0,\dots,3\}} p_{i-1,k} + 10 - 6 & \mbox{ if } j=0 \\
p_{i-1,j-1} + 7 & \mbox{ if } j=1 \\
p_{i-1,j-1} + 5 & \mbox{ if } j=2 \\
p_{i-1,j-1} + 1 & \mbox{ if } j=3 \\
\end{array} \right.
$$
Here the idea is that if in a later period the age of the machine is $0$, it means we must have bought a new machine in
the previous period. Since multiple machine states were possible in the previous period, we should do so in the state
that yields maximum profit. This is where we apply the Bellman optimality principle. In case we have a machine with a
greater age, we know for certain that we had a machine with one age smaller in the previous period and therefore, there
is nothing to optimize.
Now you can construct a table for these recurrence relations. The following python code does this in a bit of a quick-and-dirty way, and hasn't been carefully checked.
# Problem constants
profits = {0: 10, 1: 7, 2: 5, 3: 1}
cost = 6
def dp(i,j,table={}):
if (i,j) in table:
return table[(i,j)]
# Deal with the base case
if i==1:
if j==2:
table[(i,j)] = 5
else:
table[(i,j)] = float('-inf')
# Deal with the recurrent case
elif j==0:
# If we have a new machine, determine in which state it could best be bought
best = dp(i-1,0,table)
for k in range(1,4):
val = dp(i-1,k,table)
if val > best:
best = val
table[(i,j)] = best + profits[0] - cost
# If we don't have new machine, just add the profit
elif j in profits:
table[(i,j)] = dp(i-1,j-1,table) + profits[j]
# We should now have a value for the state
if (i,j) in table:
return table[(i,j)]
raise ValueError
table = {}
for k in range(0,4):
ans = dp(5,k, table)
print(k, ans)
This prints the following numbers:
$$
\begin{array}{ll}
0 & 25 \\
1 & 27 \\
2 & 25 \\
3 & 22
\end{array}
$$
which are based on the following numbers stored in the table dictionary:
$$
\begin{array}{l|rrrrr}
& 1 & 2 & 3 & 4 & 5 \\
\hline
0 & -\infty & 9 & 13 & 20 & 25 \\
1 & -\infty & -\infty & 16 & 20 & 27 \\
2 & 5 & -\infty & -\infty & 21 & 25 \\
3 & -\infty & 6 & -\infty & -\infty & 22 \\
\end{array}
$$
Which suggests that the maximum profit is obtained if you end with a 1 period old machine, and make a profit of 27000. If you want to obtain the exact policy, you would need to keep track of the predecessor states, possibly via an additional table.
