LeetCode 188. 买卖股票的最佳时机 IV
原题链接
困难
算法
(线性dp) $O(nk)$
- 最大利润 $f$ 是天数 $i$ 和交易笔数 $j$的函数,并且每天的交易有两个状态:手中
无票
或手中有票
。
- 状态表示:
$f(i, j, 0)$ 表示前 $i$ 天买卖了 $j$ 次,当前手中无票,能获取的最大利润。
$f(i, j, 1)$ 表示前 $i$ 天买卖了 $j$ 次,当前手中有票,能获取的最大利润。
- 带权的有向图:
点
表示状态
,边权
表示转移的价值增量
- 状态计算:
无票:$f(i, j, 0) = max(f(i - 1, j, 0), f(i - 1, j, 1) + w_i$
有票:$f(i, j, 1) = max(f(i - 1, j, 1), f(i - 1, j - 1 - w_i$
- 边界初值:($i: 1 \sim n, \ j: 1 \sim k$)
第 $0$ 天:$f(0, j, 0) = 0$,$f(0, j, 1) = -1e6$
第 $0$ 笔:$f(i, 0, 0) = 0$
- 边界赋值技巧:
合法则赋可取的有限值,
非法则赋负无穷或正无穷。
C++ 代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
for (int j = 0; j <= k; ++j) f[0][j][1] = -1e6;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + prices[i - 1]);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i - 1]);
}
}
return f[n][k][0];
}
};
为什么能直接返回
f[n][k][0]
呢,不应该枚举k
然后取最大值吗因为
f[n][k][0]
指的是前n天买卖了k次,当前手中无票,也就是最后的问题。棒