(Erickson 3.13) It’s almost time to show off your flippin’ sweet dancing skills! Tomorrow is the big dance contest you’ve been training for your entire life, except for that summer you spent with your uncle in Alaska hunting wolverines. You’ve obtained an advance copy of the list of n songs that the judges will play during the contest, in chronological order.
You know all the songs, all the judges, and your own dancing ability extremely well. For each integer k, you know that if you dance to the kth song on the schedule, you will be awarded exactly Score[k] points, but then you will be physically unable to dance for the next Wait[k] songs (that is, you cannot dance to songs k + 1 through k + Wait[k]). The dancer with the highest total score at the end of the night wins the contest, so you want your total score to be as high as possible. Describe and analyze an efficient algorithm to compute the maximum total score you can achieve. The input to your sweet algorithm is the pair of arrays Score[1, . . . , n] and Wait[1, . . . , n].
The question is to write a dynamic programming algorithm (ONLY PSEUDOCODE) and describe and analyze an efficient algorithm to compute the maximum total score you can achieve. the NO code is needed just the PSEUDOCODE