1
class Solution:
2
    def maxProfit(self, k: int, prices: List[int]) -> int:
3
        n = len(prices)
4
        if n <= 0:
5
            return 0
6

7
        # 当 k >= n // 2，相当于可以无限次交易
8
        if k >= n // 2:
9
            return sum(max(0, prices[i+1] - prices[i]) for i in range(n - 1))
10

11
        # 初始化三维 dp 数组: dp[i][j][0/1]
12
        # 第 i 天，最多交易 j 次，0 表示未持股，1 表示持股
13
        dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n)]
14

15
        # 初始化第 0 天的状态
16
        for i in range(n):
17
            dp[i][0][1] = float('-inf')  # 不可能持股
18
            dp[i][0][0] = 0              # 不持股的收益为 0
19

20
        for i in range(n):
21
            for j in range(k, 0, -1):
22
                if i == 0:
23
                    # 第 0 天单独处理
24
                    dp[i][j][0] = 0
25
                    dp[i][j][1] = -prices[i]
26
                    continue
27
                # 不持股：前一天就不持股 or 今天卖出股票
28
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
29
                # 持股：前一天就持股 or 今天买入（从 j-1 的不持股状态）
30
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
31

32
        return dp[n - 1][k][0]

1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n = len(prices)
4
        dp = [[0 for _ in range(2)] for _ in range(n)]
5
        for i in range(n):
6
            if i == 0:
7
                # 第 0 天：未持股为 0，持股为 -prices[0]
8
                dp[i][0] = 0
9
                dp[i][1] = -prices[i]
10
                continue
11
            if i == 1:
12
                # 第 1 天：冷冻期特殊处理
13
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
14
                dp[i][1] = max(dp[i - 1][1], -prices[i])
15
                continue
16
            # 第 i 天
17
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
18
            dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])
19
        return dp[n - 1][0]

1
class Solution:
2
    def maxProfit(self, prices: List[int], fee: int) -> int:
3
        n = len(prices)
4
        dp = [[0] * 2 for _ in range(n)]
5
        for i in range(n):
6
            if i == 0:
7
                # 第 0 天
8
                dp[i][0] = 0
9
                dp[i][1] = -prices[i] - fee
10
                continue
11
            # 不持股：昨天不持股 or 昨天持股 + 今天卖出
12
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
13
            # 持股：昨天持股 or 昨天不持股 - 今天买入 - 手续费
14
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
15
        return dp[n - 1][0]