algorithm - 最后的算法舞

[上一个相关问题：A dance with an aglorithm's complexity]
故事：我将要参加一个有n首歌的舞蹈比赛不过，我不能每首歌都跟着跳舞，因为每次跳舞前我都需要时间准备，跳舞后我也需要时间休息（幸运的是，一个舞蹈的休息时间可以与下一个舞蹈的准备时间重叠。）
我知道每一首歌我能得到什么分数，我想最大化我的总分。
所以，我有三个数组：
乐谱（i）是我能得到的随着歌曲跳舞的乐谱。
prep（i）是在歌曲i之前我必须跳过的歌曲数，否则我不能跳歌曲i（例如，如果prep（4）=2，那么除非我跳过了歌曲2和歌曲3，否则我不能跳到歌曲4）
rest（i）是我必须跳过的歌曲数，如果我跳过了歌曲i（例如，如果rest（4）=2，并且我按照歌曲4跳舞，那么我必须跳过歌曲5和歌曲6）。
预备（i）和休息（i）都没有超过上限，称之为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应该下降，正如我在链接的问题中提到的。有人能帮忙吗？这种重叠使我困惑。

最佳答案

# 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)之后的所有歌曲