algorithm - 动态规划算法

Question

我正在阅读这本教科书，试图解决一些算法以提高我的技能，但我目前遇到了这个问题:

这一章是关于动态规划的，我真的只是在开始这个问题时遇到了麻烦，因为我不知道如何解决这些类型的问题。任何人都可以帮我解决它或指出一个类似的现有算法吗？

Answer 1

这个问题的解是下面递归公式的解:

f(i) = max{ l_i + f(i+k_i) , f(i+1) }
f(x) = 0 : for all x > n

问题的解是f(1)的解。

说明:对于每一天，您都可以“跳过”这一天，并检查下一天(或后一天，...，这是通过调用 f(i+1)) - 或者吃 Lollipop ，然后你可以选择仅在 k_i 天后回来 - 这意味着你添加 f(i+k_i) 的解决方案。