题目：
给你一个 下标从 0 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i + 1 个水果需要花费的金币数目。水果超市有如下促销活动：
- 如果你花费
prices[i]购买了下标为i + 1的水果，那么你可以免费获得下标范围在[i + 1, i + i]的水果。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j - 1] 个金币去购买它以获得它的奖励。请你返回获得所有水果所需要的 最少 金币数。
示例 1：
输入：prices = [3,1,2]
输出：4
解释：
- 用
prices[0] = 3个金币购买第 1 个水果，你可以免费获得第 2 个水果。 - 用
prices[1] = 1个金币购买第 2 个水果，你可以免费获得第 3 个水果。 - 免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。
示例 2：
输入：prices = [1,10,1,1]
输出：2
解释：
- 用
prices[0] = 1个金币购买第 1 个水果，你可以免费获得第 2 个水果。 - 免费获得第 2 个水果。
- 用
prices[2] = 1个金币购买第 3 个水果，你可以免费获得第 4 个水果。 - 免费获得第 4 个水果。
示例 3：
输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
- 用
prices[0] = 26个金币购买第 1 个水果，你可以免费获得第 2 个水果。 - 免费获得第 2 个水果。
- 用
prices[2] = 6个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。 - 免费获得第 4 个水果。
- 免费获得第 5 个水果。
- 用
prices[5] = 7个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。 - 免费获得第 7 个水果。
- 免费获得第 8 个水果。
请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。
提示：
1 <= prices.length <= 10001 <= prices[i] <= 105
思路：
一、寻找子问题
我们需要解决的问题是：「获得第 1 个及其后面的水果所需要的最少金币数」。
第 1 个水果一定要买，然后呢？
第 2 个水果可以购买，也可以免费获得：
如果购买，那么需要解决的问题为：「在购买第 2 个水果的前提下，获得第 2 个及其后面的水果所需要的最少金币数」。
如果免费获得，那么根据题意，第 3 个水果必须购买，需要解决的问题为：「在购买第 3 个水果的前提下，获得第 3 个及其后面的水果所需要的最少金币数」。
无论哪种情况都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。
DP 做题技巧：见微知著，想清楚第一步（或者最后一步）怎么做，就想清楚了递归过程中的每一步要怎么做。
二、状态定义与状态转移方程
从上面的讨论可以知道，只需要一个 i 就能表达子问题，即定义 dfs(i) 表示在购买第 i 个水果的前提下，获得第 i 个及其后面的水果所需要的最少金币数。注意 i 从 1 开始。
买第 i 个水果，那么从 i+1 到 2i 的水果都是免费的。枚举下一个购买的水果 j，问题变成：在购买第 j 个水果的前提下，获得第 j 个及其后面的水果所需要的最少金币数，即 dfs(j)。
j 的范围是 [i+1,2i+1]。其中 2i+1 表示免费获得从 i+1 到 2i 的所有水果，那么第 2i+1 个水果不能免费，一定要买。
这些 dfs(j) 取最小值，再加上购买第 i 个水果的花费 prices[i]，得
dfs(i)=prices[i]+ j=i+1 min 2i+1 dfs(j)
递归边界：注意到当 2i≥n，即 i≥⌈n / 2⌉= ⌊n+1 / 2⌋ 时，后面的水果都可以免费获得了，所以递归边界为 dfs(i)=prices[i] 其中 i≥⌊n+1 / 2⌋。
递归入口：dfs(1)，这是原问题，也是答案。
由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
代码：
class Solution {
public:
int minimumCoins(vector<int>& prices) {
int n = prices.size();
vector<int> memo((n + 1) / 2);
auto dfs = [&](this auto&& dfs, int i) -> int {
if (i * 2 >= n) {
return prices[i - 1]; // i 从 1 开始
}
int& res = memo[i]; // 注意这里是引用
if (res) { // 之前算过
return res;
}
res = INT_MAX;
for (int j = i + 1; j <= i * 2 + 1; j++) {
res = min(res, dfs(j));
}
res += prices[i - 1];
return res;
};
return dfs(1);
}
};