3妹：“你不是真正的快乐， 你的笑只是你穿的保护色”
2哥 : 3妹还在唱五月天的歌啊， 你不知道五月天假唱，现在全网都在骂呢。
3妹：知道啊，可是关我什么事，这个歌的确好听啊。
2哥 : 嗯嗯，不错， 还以为你是脑残粉，无论黑白都只管追星呢。
3妹：我是只管追歌的， 歌好听就行啦。
2哥 : 追哥？追哪个哥， 难道是我这个2哥~
3妹：切，谐音梗扣钱！
2哥：话说五月天演唱会的门票还挺贵的， 要上千了， 粉丝们花了钱如果听的假唱，要伤心了。3妹会花1000块购买演唱会门票吗？
3妹：当然不会！我有钱还不多买点吃的，买点水果呢。
2哥：说到购买水果，我这里有一个关于购买水果的题目，让我来考考你吧~
2题目：
你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
如果你花费 price[i] 购买了水果 i ，那么接下来的 i 个水果你都可以免费获得。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。
请你返回获得所有水果所需要的 最少 金币数。
示例 1：
输入：prices = [3,1,2]
输出：4
解释：你可以按如下方法获得所有水果：
- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。
- 免费获得水果 3 。
注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。
购买所有水果需要最少花费 4 个金币。
示例 2：
输入：prices = [1,10,1,1]
输出：2
解释：你可以按如下方法获得所有水果：
- 花 1 个金币购买水果 1 ，然后免费获得水果 2 。
- 免费获得水果 2 。
- 花 1 个金币购买水果 3 ，然后免费获得水果 4 。
- 免费获得水果 4 。
购买所有水果需要最少花费 2 个金币。
提示：
1 <= prices.length <= 1000
1 <= prices[i] <= 10^5
2思路：
动态规划，寻找子问题
我们需要解决的问题是：「获得第 1 个及其后面的水果所需要的最少金币数」。
第 1 个水果一定要买，然后呢？
第 2 个水果可以购买，也可以免费获得：
如果购买，那么需要解决的问题为：「获得第 2 个及其后面的水果所需要的最少金币数」。
如果免费获得，那么需要解决的问题为：「获得第 3 个及其后面的水果所需要的最少金币数」。
无论哪种情况都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。
3java代码：
class Solution {
public int minimumCoins(int[] prices) {
int n = prices.length;
int[] memo = new int[(n + 1) / 2];
return dfs(1, prices, memo);
}
private int dfs(int i, int[] prices, int[] memo) {
if (i * 2 >= prices.length) {
return prices[i - 1]; // i 从 1 开始
}
if (memo[i] != 0) { // 之前算过
return memo[i];
}
int res = Integer.MAX_VALUE;
for (int j = i + 1; j <= i * 2 + 1; j++) {
res = Math.min(res, dfs(j, prices, memo));
}
return memo[i] = res + prices[i - 1]; // 记忆化
}
}