python - 动态规划 : Mission Per Day, 利润最大化调度

Question

问题:

Bob 计划工作 n 天，每天 i 都有一个任务；每个任务只持续一天，必须在指定任务的第 i 天完成，并支付给 bob x_i 美元。 Bob 一次不能完成 5 个以上的连续任务。也就是说，他必须每 5 天至少休息 1 天。

给定个数x_1...x_n，Bob应该在哪几天执行任务，在哪几天休息，以赚取尽可能多的钱并且工作不超过 5 天？您的解决方案应该是 O(n)

我的问题:

我很难想出这个问题的重现。这个问题我想了很久。我最初的想法是让 p[i] = max{x_i + x_i-1 + .... + x_i-4}，其中 p[i] 是从第 i-4 天到第 i 天可赚取的最大利润。 但是，我意识到，第一，这确实考虑到最佳解决方案可能有两个连续的工作日，第二，我没有建立以前的解决方案。

我的问题:谁能告诉我理解这个问题结构的见解？我觉得我只是不理解使解决方案易于查看的关键属性。

提前致谢!

Answer 1

每天 i 您可以选择工作并将剩余工作日减少 1 天并获利 x_i 或休息并将可用工作日重置为 5，在基本情况下，您在第 0 天有 5 个连续工作日可用.

if (remaining_rest_days == 0) {
    MaximumProfit(current_day, 0, current_profit) = MaximumProfit(current_day+1, 5, current_profit)
} else {
    MaximumProfit(current_day, remaining_rest_days, current_profit) = 
    max(
        MaximumProfit(current_day+1, remaining_rest_days - 1, current_profits + profit[current_day]),
        MaximumProfit(current_day+1, 5, current_profits)
    )
}