买卖股票的最佳时机含手续费

难度: Medium

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

1 <= prices.length <= 5 * 10⁴
1 <= prices[i] < 5 * 10⁴
0 <= fee < 5 * 10⁴

Submission

运行时间: 1004 ms

内存: 24 MB

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0, 1] for _ in range(n+1)]
        for i in range(1, n+1):
            if i == 1:
                dp[i-1][0] = 0
                dp[i-1][1] = float('-inf')
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1]-fee)
        return dp[-1][0]

Explain

这个题解使用动态规划来解决买卖股票的问题。定义状态 dp[i][0] 表示第i天不持有股票的最大利润，dp[i][1] 表示第i天持有股票的最大利润。状态转移方程为：第i天不持有股票的最大利润等于前一天不持有股票的利润和前一天持有股票但今天卖出的利润中的较大值；第i天持有股票的最大利润等于前一天持有股票的利润和前一天不持有股票但今天买入并减去手续费的利润中的较大值。最终返回最后一天不持有股票的最大利润即可。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        # 定义状态数组，dp[i][0] 表示第i天不持有股票的最大利润，dp[i][1] 表示第i天持有股票的最大利润
        dp = [[0, 1] for _ in range(n+1)]
        for i in range(1, n+1):
            if i == 1:
                # base case，第一天不持有股票的利润为0，持有股票的利润为负无穷
                dp[i-1][0] = 0
                dp[i-1][1] = float('-inf')
            # 第i天不持有股票的最大利润等于前一天不持有股票的利润和前一天持有股票但今天卖出的利润中的较大值
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1])
            # 第i天持有股票的最大利润等于前一天持有股票的利润和前一天不持有股票但今天买入并减去手续费的利润中的较大值
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1]-fee)
        # 返回最后一天不持有股票的最大利润
        return dp[-1][0]

Explore

在初始化dp数组时，将dp[i][1]的初值设置为负无穷是为了表示在第一天之前不可能持有股票，因此任何尝试计算持有股票状态的利润都应被视为非法或不可能的状态。这种设置确保了算法正确处理从未持有股票到第一次购买股票的状态转换。如果不设置为负无穷，可能会导致计算错误，认为在第一天持有股票是一个可行的状态，从而影响最终的利润计算。

选择使用两种状态（持有股票和不持有股票）是因为这样可以明确地表示每一天结束时可能的持股状态，从而简化问题的复杂度和状态转移的逻辑。这种状态设计的优势在于它直接对应于每天结束时投资者的两种可能选择：持有或不持有股票，使得状态转移直观且易于实现。与更复杂的状态设计相比，这种方法减少了状态数量，降低了实现的复杂性，并且提高了算法的效率。

状态转移方程中，dp[i][1]的转移考虑前一天不持有股票的情况减去当天的价格和手续费是为了模拟在第i天买入股票的情况。这样的设计基于买入股票需要支付股票的价格加上交易的手续费，因此从前一天的不持有状态转换到当天的持有状态时，必须扣除这些费用。这种考虑确保了利润计算的准确性，反映了实际交易中的成本影响。

在处理买卖股票问题的动态规划解法中，关键的边界条件包括初始状态的设置：第一天不持有股票的利润为0（因为没有发生交易），而第一天持有股票的利润为负无穷（因为在开始之前不可能持有股票）。在代码中，这些边界条件通过初始化dp数组时对dp[0][0]和dp[0][1]的赋值来处理，确保了状态转移的正确起点。