最后的算法舞蹈

Question

[先前有关问题：https://stackoverflow.com/questions/40706951/a-dance-with-an-aglorithms-complexity ]

故事:我要参加一场以特定顺序演唱n首歌曲的舞蹈比赛。不过，我不能每首歌都跳舞，因为我需要时间来准备每一支舞，然后再休息。(幸运的是，一个舞蹈的休息时间可能与下一个舞蹈的准备时间重叠。)

我知道我跳的每一首歌都能得到多大的分数，我想最大限度地提高我的总得分。

因此，我有三个数组：

• 乐谱(I)是我在第一首歌中跳舞所能得到的分数。
• prep(i)是我必须在歌曲#i之前跳过的歌曲数量，否则我不能唱第一首歌(例如，如果prep(4) = 2，那么除非我跳过了第2首和第3首歌，否则我就不能跳到第4首。)
• rest(i)是我必须跳过的歌曲数量，如果我跳过了歌曲#i。(例如，如果rest(4) = 2，而我跳到歌曲#4，那么我必须跳过歌曲#5和歌#6)。

无论是准备(我)还是休息(我)都不超过上限，称之为M。

怎样才能使我的分数最大化？它有多复杂？

我的尝试：

根据已经给出的答案，接受这个

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

并以此为基础，让我们有这样的死亡时间：

Opt(i + 1 + max(prep(i), rest(i)))

但我很担心，因为i应该下降，就像我在相关问题中提到的那样。有人能帮忙吗？那种重叠让我感到困惑。

Answer 1

# Get the first song that can be danced to assuming he danced to `i` and wanted to wait till prep time of a song
def myPrep(i):
    for j in range(i+1,n):
        if j - prep(j) > i:
            return j

for i in range(0,n-1):
    Opt(i) = max(Opt(i+1),
                 (Score(i) + Opt(i + 1 + rest(i))),
                 (Score(i) + Opt(i + 1 + myPrep(i)))
             )

在这种情况下，我想到了三种可能性：

• 跳过当前歌曲-> Opt(i+1)
• 与当前歌曲-> Score(i)和共舞
  • 等待ith歌曲的静息期
  • 等待第一首提供足够准备时间的歌曲-> myPrep(i)

​

我自言自语，如果我应该包括所有可能的歌曲，有足够的准备时间后，ith，但然后认为Opt(myPrep(i))应该得到正确的数字，因此，我们不需要包括所有的歌曲后，myPrep(i)在计算ith歌曲