algorithm - 动态规划算法(最小成本买苹果)

Question

您好，我正在尝试为以下问题构建一个动态编程解决方案:

鉴于一个家庭每天消耗 2kg 苹果，苹果可以使用 10 天，并且第 i 天每天 kg 苹果的价格是 p[i] ，我必须找到最小成本，这样这个家庭就不会苹果用完了。

没有 10 天的限制，我想出了解决方案，我制作了一个新数组:

locmin=p[1]
for i=2 to n 
if locmin>=p[i] then c[i]=p[i]
else locmin=p[i] c[i]=p[i]
and then 
OPT[1]=c[i]
OPT(i)=OPT[i-1]+2*c[i] (well not so much of dynamic programming but it is O(n)) .

当考虑到 10 天的限制时，我提出了一个 c[i,10] 矩阵，其中我以与以前相同的方式为每个 i-10,i 存储前 10 天窗口的最低值，并得出解决方案

OPT(i)=OPT[i-1]+2*min(p[i,j]) 0<j<=10 

.O(n^2) 解有什么想法吗？

Answer 1

我们可以做 O(n) 不只是 10 天，而是任意大小的窗口。让我们一天一次。每天，全家人吃掉 2 公斤苹果。 只有这两个kg的价格是多少？显然，它是 2 * best_price，其中 best_price = min(p[i-9...i])。

让我们保留一个堆栈。如果价格较高，我们将其添加到堆栈中，如果价格较低，我们将弹出堆栈直到较低的早期价格或堆栈为空，然后添加新价格。堆栈中的第一个元素将是最佳选择，它会在过期时被堆栈中的下一个元素替换。