题目描述：
你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
- 如果你花费
price[i] 购买了水果 i ，那么接下来的 i 个水果你都可以免费获得。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。
请你返回获得所有水果所需要的 最少 金币数。
数据范围：
$1\le prices.len \le 1000$
题解：
如果从前往后，设 $dp[i]$ 表示购买 $[0, i]$ 的所有水果，可以发现存在后效性，会对后面的状态造成影响。
消除后效性的方法就是增加状态，重新设计状态（翻转），或者高斯消元。这里肯定不需要高斯消元，好像跟期望有关的后效性用的多。这里可以增加状态，使用 $dp[i][0]$ 表示不买第 $i$ 个，买完 $[0,i]$ 的最小花费； $dp[i][1]$ 表示买第 $i$ 个，买完 $[0,i]$ 的最小花费。
则可以得到
从后往前考虑：
设 $dp[i]$ 表示购买完 $[i, n]$ 所有水果，则必须要购买第 $i$ 个水果。则需要枚举下一个购买的水果，下一个的范围为 $[i + 1, 2 \times i + 1]$ ，因为可以免费获得到 $2\times i$ ，下一个 $2 \times i + 1$ 就是必须要购买的了。
需要注意初始化， $dp[n + 1] = 0$ 。
好像也可以从前往后考虑，设 $dp[i]$ 表示买 $[0, i]$ 所有水果。枚举上一次买的是哪一个水果。对于 $dp[i]$ 来说，如果买这个 $dp[i] = dp[i - 1] + prices[i]$ .如果不买的话，需要枚举前面买的是哪个，即 $dp[i] = \min(dp[i], dp[j - 1] + prices[j])$ ，枚举上次买的是 $j$ ，其中 $j \in [\lfloor\frac{i + 1}{2}\rfloor, i - 1]$ .
也可以使用单调队列优化。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumCoins(vector<int> &prices)
{
int n = prices.size();
vector<vector<int>> dp(n + 1, vector<int>(2, INF));
dp[1][1] = prices[0];
for (int i = 2; i <= n; ++i)
{
dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + prices[i - 1];
for (int j = (i + 1) / 2; j < i; ++j)
{
dp[i][0] = min(dp[i][0], dp[j][1]);
}
}
return min(dp[n][0], dp[n][1]);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumCoins(vector<int> &prices)
{
int n = prices.size();
vector<int> dp(n + 2, INF);
dp[n] = prices[n - 1];
dp[n + 1] = 0;
for (int i = n - 1; i >= 1; --i)
{
for (int j = i + 1; j <= min(n + 1, 2 * i + 1); ++j)
{
dp[i] = min(dp[i], dp[j] + prices[i - 1]);
}
}
return dp[1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumCoins(vector<int> &prices)
{
int n = prices.size();
vector<int> dp(n + 1, INF);
dp[1] = prices[0];
dp[0] = 0;
for (int i = 2; i <= n; ++i)
{
dp[i] = dp[i - 1] + prices[i - 1];
for (int j = (i + 1) / 2; j < i; ++j)
{
dp[i] = min(dp[i], dp[j - 1] + prices[j - 1]);
}
}
return dp[n];
}
};
|