What is the key pattern to solve Best Time to Buy and Sell Stock with Transaction Fee?

The main pattern is state transition dynamic programming, tracking maximum profit while holding or not holding stock.

How do I account for transaction fees in this problem?

Subtract the fee from the profit whenever you sell a stock, updating your cash state accordingly.

Can I use greedy without dynamic programming?

Pure greedy fails for complex sequences; the correct approach combines greedy updates with state transitions to account for fees.

What is the time and space complexity of this solution?

Time complexity is O(n) for iterating prices once, and space complexity is O(1) using only two variables.

Why can't I hold multiple stocks simultaneously in this problem?

The problem constraints allow only one stock per transaction cycle, ensuring state transitions remain valid.

#714

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给定一个整数数组 prices ，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买…

数组动态规划贪心

题目描述

给定一个整数数组 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⁴

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j)$ ，表示从第 $i$ 天开始，状态为 $j$ 时，能够获得的最大利润。其中 $j$ 的取值为 $0, 1$ ，分别表示当前不持有股票和持有股票。答案即为 $dfs(0, 0)$ 。

函数 $dfs(i, j)$ 的执行逻辑如下：

如果 $i \geq n$ ，那么没有股票可以交易了，此时返回 $0$ ；

否则，我们可以选择不交易，此时 $dfs(i, j) = dfs(i + 1, j)$ 。我们也可以进行股票交易，如果此时 $j \gt 0$ ，说明当前持有股票，可以卖出，此时 $dfs(i, j) = prices[i] + dfs(i + 1, 0) - fee$ ；如果此时 $j = 0$ ，说明当前不持有股票，可以买入，此时 $dfs(i, j) = -prices[i] + dfs(i + 1, 1)$ 。取最大值作为函数 $dfs(i, j)$ 的返回值。

答案为 $dfs(0, 0)$ 。

为了避免重复计算，我们使用记忆化搜索的方法，用一个数组 $f$ 记录 $dfs(i, j)$ 的返回值，如果 $f[i][j]$ 不为 $-1$ ，说明已经计算过，直接返回 $f[i][j]$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $prices$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each price is processed once, updating constant state variables. Space complexity is O(1) since only two variables are maintained regardless of input size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a clear state representation separating holding vs not holding stock.
question_mark
Expect efficient O(n) solution rather than nested loops for multiple transactions.
question_mark
Check for correct handling of the transaction fee on each sell operation.

warning

常见陷阱

外企场景

error
Forgetting to subtract the transaction fee when updating cash after a sell.
error
Using extra arrays for all states, increasing space complexity unnecessarily.
error
Mixing the order of updates for hold and cash, leading to incorrect state transitions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Restrict number of transactions to K and adapt the state transition DP accordingly.
arrow_right_alt
Introduce cooldown periods after selling, requiring additional state tracking.
arrow_right_alt
Allow multiple stocks with independent fees, extending the DP state dimensions.

help

常见问题

外企场景

继续练习

#646 最长数对链 #871 最低加油次数 #435 无重叠区间