题目描述：
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
数据范围：
$1\le k \le 100; 1\le prices.len \le 1000$
题解：
类似之前做过的标签: 状态机 | Luobuyu’s Blog，需要为每一天设置所有的可能状态，然后在不同天（连续的）的状态之间转换。
这个是比较普遍的问题，需要设置 $2 \times k$ 个状态，其中 $2 \times i$ 表示第 $i$ 次持有股票， $2\times i + 1$ 表示第 $i$ 次卖出，不持有。
用 $dp[k][0/1]$ 表示持有与不持有，则
其中在第 $j$ 天时，如果持有股票，说明是之前买入的或者当天买入的，如果是之前买入的就是 $dp[i][0]$ ，当天买入的就是上次卖了之后，这次花费 $prices[j]$ 买入 $dp[i-1][1] - prices[j]$ ；如果不持有股票，说明之前就卖出了或者是当天卖出的，之前卖出 $dp[i][1]$ ，当天卖出 $dp[i][0] + prices[j]$ 。
代码：
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
33
34
35
36
| 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 = 1e2 + 10;
const int INF = 0x3f3f3f3f;
int dp[maxm][2];
int maxProfit(int k, vector<int> &prices)
{
int n = prices.size();
for (int i = 0; i < k; ++i)
{
dp[i][0] = -prices[0];
dp[i][1] = 0;
}
for (int i = 1; i < n; ++i)
{
dp[0][0] = max(dp[0][0], -prices[i]);
dp[0][1] = max(dp[0][1], dp[0][0] + prices[i]);
for (int j = 1; j < k; ++j)
{
dp[j][0] = max(dp[j][0], dp[j - 1][1] - prices[i]);
dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);
}
}
return dp[k - 1][1];
}
};
|