algorithm - 如何使用动态规划最大化单位(即本例中的薪水)？

Question

这是一道面试题

There is a series of days D1, D2,...Dn that you can choose to work. Each working i-th day you are paid with a salary Si. If you work in day Di, then you could not work for the following Ni days right after. Maximize your salary using DP.

下面是我想出的解决方案:

让 OPT (i) 表示第 Di 天的最高工资。我是否在第 i 天工作有两种可能性。我的递归公式:OPT (i) = max (OPT(i-Ni)+Si, OPT(i-1)

Maximize_salary(n)
Initialize my array M[i] = 0 for i <= 0
for i = 1 to n
  M[i] = max(M[i-Ni]+Si, M[i-1])
end for
return M[n]

我的方法正确吗？我担心 for 循环间隔，因为我使用的是 i-Ni。我是否需要将数组 M 中的所有值初始化为 Ni？

我认为我的算法的复杂度是 O(n)。

Answer 1

您的方法是正确的，尽管您可以简单地检查您尝试访问的 M[k] 是否存在，如果不存在则返回 0。此外，如果今天是 d 日，并且您已经 r 天没有工作，那么您可以工作的最后一天是 d - r - 1。

    def maximizeSalary(M, N, S, n):
        def getM(index):
            if index < 0: return 0 else: return M[index]

        for i = 0 to n - 1:
            M[i] = max(getM(i - N[i] - 1) + S[i], getM(i - 1))