给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。
你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：
- 普通交易：在第
i天买入，然后在之后的第j天卖出，其中i < j。你的利润是prices[j] - prices[i]。 - 做空交易：在第
i天卖出，然后在之后的第j天买回，其中i < j。你的利润是prices[i] - prices[j]。
注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。
通过进行 最多 k 笔交易，返回你可以获得的最大总利润。
示例 1:
输入: prices = [1,7,9,8,2], k = 2
输出: 14
解释:
我们可以通过 2 笔交易获得 14 美元的利润：
- 一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。
- 一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。
示例 2:
输入: prices = [12,16,19,19,8,1,19,13,9], k = 3
输出: 36
解释:
我们可以通过 3 笔交易获得 36 美元的利润：
- 一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。
- 一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。
- 一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。
提示:
2 <= prices.length <= 10^31 <= prices[i] <= 10^91 <= k <= prices.length / 2
思路
相较于前面几题，多了一种状态。
- 今天没持有(stat=0)
- 今天持有了(stat=1)
- 今天倒欠了(stat=2)。因为要做空，要先卖掉，未来再买回来。
来看第i天的状态，
- 没持有
- i-1天也没持有
- i-1天持有了，i天卖了，因此获得收益price[i]
- i-1天倒欠了，i天买回，因此付出price[i]
- 持有了
- i-1天也持有
- i-1天没持有，i天买入，因此付出price[i]
- 倒欠
- i-1天也倒欠
- i-1天没持有，i天卖了，因此获得price[i]
代码
class Solution {
public:
// DP with memory
long long maximumProfit0(vector<int>& prices, int k) {
const int n = prices.size();
vector memo = vector<vector<vector<long long>>> (n, vector<vector<long long>>(
k + 1, vector<long long>(
3, LONG_LONG_MIN / 2
)
));
function<long long(int,int,int)> dfs = [&](int i, int k, int st) -> long long {
// base
if (i < 0) return st == 1 ? INT_MIN : 0;
if (k == 0) return 0;
auto& m = memo[i][k][st];
if (m == LONG_LONG_MIN / 2) {
if (st == 0) {
m = max({dfs(i-1, k, 0), dfs(i-1, k, 1) + prices[i], dfs(i-1, k, 2) - prices[i]});
}
if (st == 1) {
m = max(dfs(i-1, k, 1), dfs(i-1, k-1, 0) - prices[i]);
}
if (st == 2) {
m = max(dfs(i-1, k, 2), dfs(i-1, k-1, 0) + prices[i]);
}
}
return m;
};
return dfs(n - 1, k, 0);
}
long long maximumProfit(vector<int>& prices, int k) {
using LL = long long;
const int n = prices.size();
// hold, k, n
vector f = vector<vector<vector<LL>>>(3, vector<vector<LL>>(
k + 1, vector<LL>(n + 1, 0)
));
// base
for (auto& hold_k : f[1]) {
hold_k[0] = INT_MIN;
}
for (int i = 1; i <= n; ++i) {
int p = prices[i-1];
for (int ik = 1; ik <= k; ++ik) {
f[0][ik][i] = max({f[0][ik][i-1], f[1][ik][i-1] + p, f[2][ik][i-1] - p});
f[1][ik][i] = max(f[1][ik][i-1], f[0][ik-1][i-1] - p);
f[2][ik][i] = max(f[2][ik][i-1], f[0][ik-1][i-1] + p);
}
}
return f[0][k][n];
}
};see also