Readme

2969.Minimum-Number-of-Coins-for-Fruits-II

对于前i件物品而言，我们令dp[i][0]表示第i个水果不付款的最小代价，dp[i][1]表示第i个水果付款的最小代价。显然，我们容易得出

dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + prices[i]

那么对于dp[i][0]而言，第i个水果不用付款，必然是因为某第j个水果付款的缘故（需要满足2*j>=i）。这样的j可能有多个

dp[i][0] = min(dp[i-1][j])  j=(i+1)/2, (i+1)/2+1, ..., i-1.

显然，这是求一个滑动窗口的最小值，使用双端队列deque的套路：我们维护一个递增的deque，里面盛装的是dp[x][1]的值。当队首元素不满足2*j>=i时就不断弹出，最终队首元素就是合法滑窗内的最小值，即给dp[i][0]赋值。然后将dp[i][1]入队，并将所有队尾元素大于等于dp[i][1]的都弹出，这是因为它们在数值大小或序列先后上都不及第i物品。