假设您有一个数组，其中第 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) {}
原始版本非常简单，但我不确定如何处理这个修改后的版本。谁能给我一些提示/指导？我正在研究面试的算法问题。
这个问题可以通过应用动态规划技术来解决。
让我们为这个问题建立一个递归公式。
从第一天开始，我们将迭代到最后一天。每天，我们需要做出两种情况的决定：
- 要么我们手里有一只股票，我们需要决定是否持有它到第二天，或者我们卖掉它并获得一些利润
- 或者我们没有任何库存，我们需要决定是购买还是等到第二天。
所以，这是公式，假设我们现在是白天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 and have_stock=>我们可以使用一个简单的dp[n][2]表来存储结果。时间复杂度将为O(n)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
