一個與aglorithm複雜的舞蹈

我即將參加舞蹈比賽，明天是大日子！我知道apriori與比賽的歌曲n和他們的順序列表。經過多次偵察之後，我能夠判斷評委和我的技巧如此出色，以至於如果我跳出列表中的第i首歌曲，即score(i)，我可以準確地預測出我的結果。一個與aglorithm複雜的舞蹈

然而，在第i首歌曲之後，我需要時間休息，即我不能跳舞下一首rest(i)歌曲，即歌曲i + 1，...，i + rest（i）。我可以跳舞的歌曲數量不存在其他限制。給出一個有效的算法來計算理想的最大總分及其複雜度。

所以我認爲應該遞歸使用，其中max(i) = max(i + 1)或，然後挑選出最好的出這兩個以每一步。有人可以幫忙嗎？

2016-11-20 gsamaras

你的想法聽起來不錯，你在尋找什麼樣的幫助？ – BlackBear

@BlackBear我所描述的嘗試看起來不像算法。我希望有人能夠幫助我將我的想法擴展到算法，並且如果能夠的話，爲複雜性提供一個提示（但是我認爲一旦我們生成它就可以從算法中得出結論）。 :) – gsamaras

從基本情況開始。你回報什麼價值？ –

讓我們有n首歌曲索引爲0..n-1。考慮到我們可以從歌曲i開始自由跳舞，讓Opt（i）成爲最高總分。對於選項復發是

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

直觀地說，我們要麼不跳舞的歌曲我和得到的剩餘時間的價值，或者我們做什麼，得分首歌我，休息和休息後得到的時間價值。

此遞歸應評估爲我降序，與先前計算的值緩存在一個數組中。運行時間是O（n）。

2016-11-20 18:22:27

謝謝，舞蹈繼續，最後一步，[檢查它是否有一些時間]（http://stackoverflow.com/questions/40709017/the-last-algorithmic-dance）。 – gsamaras

遞歸會，

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

其中，

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

編輯1：添加解釋

基本情況是參與者不會跳舞所以總比分將是0

否則，他要麼跳舞，要麼不跳舞某首歌。所以決定歸結爲他是否應該在這首歌中跳舞，以便最終得分最大化。

如果他決定去跳舞，他將獲得score(i)，不能跳舞rest(i)因此剩下的最大可能得分會的score(i) + DP(i + rest(i))

值。如果他決定不跳舞這首歌，將比分DP(i+1) 。

因爲我們想要最大化分數，我們選擇這兩個值的最大值。

2016-11-20 17:33:45 Aditya

感謝您的更新！舞會繼續，最後一步，[檢查它是否有一些時間]（http://stackoverflow.com/questions/40709017/the-last-algorithmic-dance）。 – gsamaras

回答