买卖股票修改版的最佳时机

Question

假设您有一个数组，其中第 i 个元素是给定股票在第 i 天的价格。

如果您可以无限次买卖（一次只能持有一只股票），但每次卖出都需要支付交易费，请计算您能获得的最大利润。

样本输入 { 1, 3, 7, 5, 10, 3 } 费用 = 3。

如果您进行两笔交易，总利润为 (7 - 1) - 3 + (10 - 5) - 3 = 5。如果您只进行一笔交易，总利润为 (10 - 1) - 3 = 6。

public int maxProfit(int[] prices, int fee) {}

原始版本非常简单，但我不确定如何处理这个修改后的版本。谁能给我一些提示/指导？我正在研究面试的算法问题。

Answer 1

这个问题可以通过应用动态规划技术来解决。

让我们为这个问题形成一个递归公式。

从第一天开始，我们将迭代到最后一天。对于每一天，我们需要做出两种决定：

• 要么我们手上有一只股票，我们需要决定是否持有到第二天，或者我们卖掉它并获得一些利润
• 或者我们没有任何库存，我们需要决定是买一个还是等到第二天。

所以，这是公式，假设我们在白天 current_day

int result = 0;
if have_stock{
    result = max(prices[current_day] - fee + f(current_day + 1, no_stock), f(current_day + 1, have_stock));
}else{
    result = max(-price[current_day] + f(current_day + 1, have_stock) , f(current_day + 1, no_stock));
}

现在，我们看到，问题可以用两个变量来表示，current_day并且have_stock=> 我们可以用一个简单的dp[n][2]表来存储结果。时间复杂度为O(n)