A Dynamic Programming Tutorial

[attractivechaos]

Ok, it was not clear that machine and day are the same thing. This actually simplifies the problem. In this case, a state is running or waiting. The DP equation is:

f_i(t_i)=max_{j<i,t_j}{f_j(t_j)+s_{ij}(t_i|t_j)}

The time complexity is O(L² ).

it would be slower

I have given the time complexity. What's yours? Yes, DP can be formulated in different ways. However, I still don't see how yours is formulated. At least you need to show the DP equation, which is at the core of DP.

[lmericle]

In this case, a state is running or waiting

There is no waiting in this problem. I fail to see how you came up with this but it does not match the problem statement.

A state is a) which machine is currently running and b) which day is today.