[ Previous related question: A dance with an aglorithm's complexity ]
The story: I'm about to take part in a dance contest with n songs in a specific order. I can't dance to every single song, though, because I need time to prepare before each dance, and time to rest afterward. (Fortunately, the rest time from one dance can overlap with the preparation time for the next.)
I know what score I can get for each song I do dance to, and I want to maximize my total score.
So, I have three arrays:
- score(i) is the score I can get for dancing to song #i.
- prep(i) is the number of songs I have to skip immediately before song #i, or else I can't do song #i. (For example, if prep(4) = 2, then I can't dance to song #4 unless I've skipped both song #2 and song #3.)
- rest(i) is the number of songs I have to skip immediately after song #i, if I did song #i. (For example, if rest(4) = 2, and I dance to song #4, then I have to skip both song #5 and song #6.)
Neither prep(i) nor rest(i) ever exceeds an upper bound, call it M.
How can I maximize my score? What's its complexity?
My attempt:
Based on the answer already given, take that
Opt(i) = max(Opt(i+1),
Score(i) + Opt(i + 1 + rest(i))) for i = 0..n-1.
and build on it, so that we have as a dead time something like:
Opt(i + 1 + max(prep(i), rest(i)))
but I am worried, since i
should descend, as mentioned in my linked question. Can anybody help please? That overlapping confuses me.