algorithm - 与算法的复杂性共舞

Question

我即将参加舞蹈比赛，明天是重要的日子!我先验地知道带有 n 的列表比赛歌曲及其顺序。经过多次考察，我能够确定评委和我的技能，如果我跳列表中的第 i 首歌曲，即 score(i)，我可以准确预测我的结果。 .

然而，在第 i 首歌之后，我需要时间休息，即我不能跳下一首 rest(i)歌曲，即歌曲 i + 1, ..., i + rest(i)。我可以跳舞的歌曲数量没有其他限制。给出一个有效的算法来计算您理想的最大总分及其复杂性。

---

所以我认为应该使用递归，其中max(i) = max(i + 1)或 max(i) = score(i) + max(i + 1 + rest(i))然后在每一步都从这两个中选出最好的。有人可以帮忙吗？

Answer 1

让 n 首歌曲索引为 0..n-1。让 Opt(i) 成为最大总分，因为我们可以从歌曲 i 开始自由跳舞。 Opt 的递归是

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

直觉上，我们要么不跳歌曲 i 并获取剩余时间的值，要么跳歌曲 i 打分，休息，并获取休息后的时间值。

应该对递减的 i 进行评估，并将先前计算的值缓存在数组中。运行时间为O(n)。