문제 설명
aglorithm의 복잡성을 가진 춤 (A dance with an aglorithm's complexity)
저는 댄스 콘테스트에 참가하려고 하는데 내일이 중요한 날입니다! 나는 경연의 n곡의 목록과 순서를 선험적으로 알고 있습니다. 많은 스카우트 끝에 심사위원과 실력을 판단할 수 있어서 목록의 i번째 곡, 즉 score(i)를 춤을 추면 결과를 정확하게 예측할 수 있었습니다.score(i). p>
그러나 i 번째 곡 이후에는 휴식 시간이 필요합니다. 즉, 다음 rest(i) 곡, 즉 i + 1, ..., i 곡은 춤을 출 수 없습니다. + 휴식(i). 내가 춤출 수 있는 노래의 수에 대한 다른 제약은 없습니다. 이상적인 최대 총점과 복잡성을 계산하기 위한 효과적인 알고리즘을 제공하십시오.
그래서 재귀를 사용해야 한다고 생각합니다. 여기서 max(i) = max(i + 1)</코드> 또는 <코드> max(i) = score(i) + max(i + 1 + rest(i)) 그런 다음 모든 단계에서 이 두 가지 중에서 가장 좋은 것을 선택합니다. 누군가 도울 수 있습니까?
참조 솔루션
방법 1:
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.
방법 2:
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).
(by gsamaras、Aditya、David Eisenstat)