1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n = len(prices)
4
        dp = [[0] * 2 for _ in range(n)]
5
        for i in range(n):
6
            if i - 1 == -1:
7
                # base case
8
                dp[i][0] = 0  # 第一天没有持有股票，利润为 0
9
                dp[i][1] = -prices[i]  # 第一天买入股票，花费 prices[i]
10
                continue
11
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])  # 昨天没持有 vs 昨天持有今天卖出
12
            dp[i][1] = max(dp[i - 1][1], -prices[i])  # 昨天持有 vs 今天重新买入（只能买一次）
13
        return dp[n - 1][0]

1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n = len(prices)
4
        dp = [[0] * 2 for _ in range(n)]
5
        for i in range(n):
6
            if i - 1 == -1:
7
                # base case
8
                dp[i][0] = 0  # 第一天不持有股票，利润为 0
9
                dp[i][1] = -prices[i]  # 第一天持有股票（买入）
10
                continue
11
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])  # 昨天不持有 vs 昨天持有今天卖出
12
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])  # 昨天持有 vs 今天买入（可以多次交易）
13
        return dp[n - 1][0]

1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        max_k = 2  # 最多两次交易
4
        n = len(prices)
5
        dp = [[[0 for _ in range(2)] for _ in range(max_k + 1)] for _ in range(n)]
6
        for i in range(n):
7
            for k in range(max_k, 0, -1):
8
                if i - 1 == -1:
9
                    # base case
10
                    dp[i][k][0] = 0  # 第一天不持股
11
                    dp[i][k][1] = -prices[i]  # 第一天持股
12
                    continue
13
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])  # 不持股 or 今天卖出
14
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])  # 持股 or 今天买入（消耗一次交易）
15
        return dp[n - 1][max_k][0]