本文涉及知识点

C++动态规划

LeetCode2944. 购买水果需要的最少金币数

你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
如果你花费 price[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。
请你返回获得所有水果所需要的 最少 金币数。
示例 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 <= 1000
1 <= prices[i] <= 10⁵

动态规划

动态规划的状态表示

dp[i] 表示购买及赠送前i项商品的最小花费。空间复杂度：O(n)

动态规划的填表顺序

枚举前置状态
for i = 0 to n-1

动态规划的转移方程

j $\in$[i,2*i+1]
MinSelf(dp[j+1],dp[i] + price[i])
单个状态的时间复杂度：O(n)，总时间复杂度：O(nn)。

动态规划的初始值

dp[0]=0，其它全是是INT_MAX/2。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int minimumCoins(vector<int>& prices) {
				const int N = prices.size();
				vector<int> dp(N + 1, INT_MAX / 2);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < min(2 * i + 2, N); j++) {
						dp[j + 1] = min(dp[j + 1], dp[i] + prices[i]);
					}
				}
				return dp.back();
			}
		};

单元测试

	vector<int> prices;
		TEST_METHOD(TestMethod11)
		{
			prices = { 3, 1, 2 };
			auto res = Solution().minimumCoins(prices);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			prices = { 1,10,1,1 };
			auto res = Solution().minimumCoins(prices);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			prices = { 26,18,6,12,49,7,45,45 };
			auto res = Solution().minimumCoins(prices);
			AssertEx(39, res);
		}