A dance with an aglorithm's complexity

问题:

I am about to take part in a dance contest and tomorrow is the big day! I know apriori the list with the n songs of the contest and their order. After much scouting, I was able to determine the judges and my skills so good that I can accurately predict my result if I dance the i-th song of the list, i.e. score(i).

However, after the i-th song, I need time to rest, namely I cannot dance the next rest(i) songs, i.e. songs i + 1, ..., i + rest(i). No other constraint exists for the number of songs I can dance. Give an effective algorithm for computing your ideally maximum total score and its complexity.

---

So I think that recursion should be used, where max(i) = max(i + 1) or max(i) = score(i) + max(i + 1 + rest(i)) and then pick the best out of this two at every step. Can someone help?

回答1:

Let there be n songs indexed 0..n-1. Let Opt(i) be the maximum total score given that we're free to dance starting on song i. The recurrence for Opt is

Opt(n) = 0
Opt(i) = max(Opt(i+1),
             Score(i) + Opt(i + 1 + Rest(i))) for i = 0..n-1.

Intuitively, we either don't dance song i and get the value of the remaining time, or we do, score song i, rest, and get the value of the time after resting.

This recurrence should be evaluated for i descending, with the previously calculated values cached in an array. The running time is O(n).

回答2:

Recursion would be,

for i: 1 -> n
    DP(n) = max(0,(score(i)+DP(i+r)),DP(i+1)) 

where,

r = resting interval
0 is the situation where it is better not to dance at all :)

Edit 1: Adding explanation

Base case is participant doesn't dance so the total score will be 0

Otherwise, he either dances or not on a particular song. So the decision boils down to if he should dance on this song or not so that the ultimate score is maximized.

If he decided to dance, he will gain score(i) and cannot dance for rest(i) so the remaining max possible score will be the value of score(i) + DP(i + rest(i))

If he decides not to dance on this song, the score will be DP(i+1).

Because we want to maximize the score, we pick the max of these two values.