LeetCode 买卖股票最佳时机含手续费题解

LeetCode 买卖股票最佳时机含手续费题解题目描述给定一个整数数组 prices其中第 i 个元素表示第 i 天的股票价格。设计一个算法计算出最大利润。你可以无限次地完成交易但是每次交易都需要手续费。示例输入prices [1, 3, 2, 8, 4, 9],fee 2输出8解题思路方法动态规划思路使用动态规划维护两种状态持有现金和持有股票。持有现金之前就已经不持有股票或者今天卖出了股票。持有股票之前就持有股票或者今天买入了股票。复杂度分析时间复杂度O(n)。空间复杂度O(1)。代码实现def max_profit(prices, fee): cash 0 hold -prices[0] for i in range(1, len(prices)): cash max(cash, hold prices[i] - fee) hold max(hold, cash - prices[i]) return cash # 测试 def test_max_profit(): prices [1, 3, 2, 8, 4, 9] fee 2 print(max_profit(prices, fee)) # 输出8 if __name__ __main__: test_max_profit()总结买卖股票最佳时机含手续费是动态规划的典型应用通过维护持有现金和持有股票两种状态来计算最大利润。