求最多买卖多次没交集(下一次买入前必须先卖出上一次的股票)且每次买卖支付一次手续费的股票的最大利润。
参考“188. 买卖股票的最佳时机 IV”。
状态表示:
f(i, j) 表示在前下标i天卖完或已买但没卖股票时所获得的最大利润。
f(i, 0) 表示在前下标i天卖完股票时所获得的最大利润。
f(i, 1) 表示在前下标i天已买但没卖股票时所获得的最大利润。
状态计算:
f(i, 0) = max{f(i - 1, 0), f(i - 1, 1) + a[i]}
f(i, 1) = max{f(i - 1, 1), f(i - 1, 0) - a[i] - fee}
决策:
在第下标i天不卖或卖股票:
不卖,即f(i, 0) = f(i - 1, 0) 。
卖,即f(i, 0) = f(i - 1, 1) + a[i] 。
在第下标i天不买或买股票:
不买,即f(i, 1) = f(i - 1, 1) 。
买,即f(i, 1) = f(i - 1, 0) - a[i] - fee 。
时间复杂度:O(n) ;空间复杂度:O(2n) 。
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][1] = -prices[0] - fee;
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
}
return dp[n - 1][0];
}
}