Day44 | 动态规划：状态机DP 买卖股票的最佳时机IV && 买卖股票的最佳时机III

在动态规划（DP）问题中，“买卖股票的最佳时机”类问题经常出现在面试和算法竞赛中。今天我们将重点讲解两个经典的股票买卖问题：《买卖股票的最佳时机IV》和《买卖股票的最佳时机III》。这两个问题都可以通过动态规划和状态机方法求解。

一、问题描述与分析

1.1 买卖股票的最佳时机III

问题描述：

给定一个数组 prices，其中 prices[i] 是第 i 天的股票价格。你最多可以进行 两次 交易，且每次交易必须先买入再卖出，求最大利润。

输入：

• 整数数组 prices，长度为 n，表示股票每天的价格。

输出：

• 返回可以获得的最大利润。

示例：

textCopy Code
输入: prices = [3,2,6,5,0,3]
输出: 7
解释: 在第 2 天买入， 第 3 天卖出，利润为 6 - 2 = 4。
      然后在第 5 天买入， 第 6 天卖出，利润为 3 - 0 = 3。
      总利润 = 4 + 3 = 7。

思路：

这个问题的核心是如何管理股票的买入与卖出次数。由于最多允许两次交易，我们可以使用动态规划来解决。

1.2 买卖股票的最佳时机IV

问题描述：

给定一个数组 prices，其中 prices[i] 是第 i 天的股票价格。你最多可以进行 k 次交易，且每次交易必须先买入再卖出，求最大利润。

输入：

• 整数 k：最多允许的交易次数。
• 整数数组 prices，长度为 n，表示股票每天的价格。

输出：

• 返回可以获得的最大利润。

示例：

textCopy Code
输入: k = 2, prices = [2,4,1]
输出: 2
解释: 在第 1 天买入， 第 2 天卖出，利润为 4 - 2 = 2。

思路：

这个问题的核心是限制交易次数的情况下如何求解最大利润。类似于问题 III，但这里的交易次数是动态的。

二、解题思路：状态机 DP

在这两个问题中，我们的目标是使用动态规划（DP）来求解股票买卖的最大利润。在这类问题中，状态机模型是一个很好的框架。

2.1 状态定义与转换

买卖股票的最佳时机III

我们定义一个 dp 数组，其中 dp[i][j] 表示在第 i 天，进行了最多 j 次交易时的最大利润。

• i 代表天数。
• j 代表交易次数，最大为 2。

状态转移方程可以分为以下几种情况：

• 不进行交易：dp[i][j] = dp[i-1][j]。
• 进行买入交易：dp[i][j] = max(dp[i][j], dp[i-1][j-1] - prices[i])。
• 进行卖出交易：dp[i][j] = max(dp[i][j], dp[i-1][j] + prices[i])。

买卖股票的最佳时机IV

在此问题中，最多进行 k 次交易。我们仍然使用 dp[i][j] 表示在第 i 天，进行了最多 j 次交易时的最大利润。

• i 代表天数。
• j 代表交易次数，最大为 k。

状态转移方程与问题 III 类似，只是将交易次数扩展到 k。

2.2 具体实现

买卖股票的最佳时机III（最多两次交易）

我们首先来实现买卖股票的最佳时机 III。

pythonCopy Code
def maxProfit(prices):
    if not prices:
        return 0
    
    n = len(prices)
    # dp[i][j] 表示第 i 天，最多 j 次交易时的最大利润
    dp = [[0] * 3 for _ in range(n)]  # 2 次交易，所以 j = 1, 2

    for j in range(1, 3):  # 最大两次交易
        max_diff = -prices[0]  # max_diff 表示买入的最大利润
        for i in range(1, n):
            dp[i][j] = max(dp[i-1][j], prices[i] + max_diff)
            max_diff = max(max_diff, dp[i][j-1] - prices[i])

    return dp[n-1][2]

# 示例
prices = [3, 2, 6, 5, 0, 3]
print(maxProfit(prices))  # 输出: 7

买卖股票的最佳时机IV（最多k次交易）

接下来，我们实现买卖股票的最佳时机 IV。

pythonCopy Code
def maxProfit(k, prices):
    if not prices:
        return 0
    
    n = len(prices)
    
    if k >= n // 2:
        # 如果交易次数 k 大于等于股票天数的一半，那么可以任意买卖，直接计算所有的利润
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))
    
    dp = [[0] * (k+1) for _ in range(n)]
    
    for j in range(1, k+1):
        max_diff = -prices[0]
        for i in range(1, n):
            dp[i][j] = max(dp[i-1][j], prices[i] + max_diff)
            max_diff = max(max_diff, dp[i][j-1] - prices[i])
    
    return dp[n-1][k]

# 示例
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices))  # 输出: 2

2.3 时间复杂度与空间复杂度分析

• 时间复杂度：O(n*k)，其中 n 为股票的天数，k 为最多的交易次数。在最坏情况下，两个问题的时间复杂度分别为 O(n*2) 和 O(n*k)。
• 空间复杂度：O(n*k)，用于存储动态规划表格。

三、动态规划的优化

虽然上述方法能够解决问题，但其空间复杂度为 O(n*k)，可以通过优化空间复杂度来进一步提高性能。通过使用滚动数组或状态压缩技术，我们可以将空间复杂度降低到 O(k)。

3.1 状态压缩（滚动数组）

对于 DP 题目，如果每次状态只依赖于前一层的状态，那么我们可以通过滚动数组优化空间复杂度。以下是状态压缩的实现：

买卖股票的最佳时机III（优化空间复杂度）

pythonCopy Code
def maxProfit(prices):
    if not prices:
        return 0
    
    n = len(prices)
    dp = [[0] * 3 for _ in range(2)]  # 只有 2 层状态

    for j in range(1, 3):
        max_diff = -prices[0]
        for i in range(1, n):
            dp[j % 2][i % 2] = max(dp[j % 2][i-1], prices[i] + max_diff)
            max_diff = max(max_diff, dp[j % 2][i-1] - prices[i])

    return dp[1][2]

# 示例
prices = [3, 2, 6, 5, 0, 3]
print(maxProfit(prices))  # 输出: 7

买卖股票的最佳时机IV（优化空间复杂度）

pythonCopy Code
def maxProfit(k, prices):
    if not prices:
        return 0
    
    n = len(prices)
    
    if k >= n // 2:
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))
    
    dp = [0] * (k+1)
    for j in range(1, k+1):
        max_diff = -prices[0]
        for i in range(1, n):
            dp[j] = max(dp[j], prices[i] + max_diff)
            max_diff = max(max_diff, dp[j-1] - prices[i])

    return dp[k]

# 示例
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices))  # 输出: 2

3.2 进一步的优化

除了空间压缩，我们还可以在极端情况下做一些优化。例如，当股票价格走势较为平稳，或者我们允许的交易次数 k 比股票的天