2944

线性dp 规定dp[i] = 购买完[0, i - 1]时 (购买i的价格，通过前面的购买免费获得i的价格) 题目规定买第i位后面i+1位可以享受免费，结合n = 1000不难得出在购买第i位时同时更新买与不买的两个。其中购买选项可以直接得到, 即dp[i+1][buy] = min(dp[i][buy], dp[i][dont buy] + prices[i] 因为购买选项只能通过前面一个获得(题目要求，购买所有)。而免费获得选项则需要获取到前面数位满足条件的购买选项 综合下来时间复杂度: $\mathcal{O}(n^2)$

利用单调队列

我们在购买第i位时可以知道它后面的i + 1位都能免费获得，假设我们像这样存起来这个index，那么我们到j位时就可以通过container中的index判断我们是否能免费获得当前。在我们顺序添加中，不难看出queue是个很好的container选择，使用queue时我们可以将头与当前index作比较看看在不在区间内来。 此外虽然我们知道queue中购买index都可以免费获得当前，但是问题在于哪个价位的免费领最划算？不如我们直接维护一个单调队列，直接取最前面即可。那么如何维护单调性呢？因为我们要买queue中的物品才能免费， 结合前面购买只需看前一个的结论这意味着我们需要比较queue中idx的值dp[idx - 1] + prices[idx]