章节 48 | 面试题：股票买卖系列

在算法面试中，股票买卖问题是一类经典且富有挑战性的动态规划问题，它们不仅考验了候选人对算法设计的深刻理解，还考察了其在复杂情境下的逻辑思维和问题解决能力。这类问题通常围绕如何在给定的股票价格序列中，通过一系列买入和卖出操作，实现最大利润展开。本章节将深入探讨几个典型的股票买卖问题，包括“一次交易”、“多次交易”、“含冷冻期”以及“含交易费”的变体，通过详细分析和代码实现，帮助读者掌握解决这类问题的关键思路。

48.1 一次交易

问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路分析：这个问题看似复杂，但实际上可以简化为寻找价格序列中的一个“低谷”和一个随后的“高峰”，计算两者之间的差值即为最大利润。使用动态规划可以更优雅地解决此问题。定义dp[i][0]表示第i天不持有股票时的最大利润，dp[i][1]表示第i天持有股票时的最大利润。则有状态转移方程：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])（今天不持股，要么昨天也不持股，要么昨天持股今天卖出）
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])（今天持股，要么昨天就持股，要么昨天不持股今天买入）

代码实现（优化空间复杂度至O(1)）：

def maxProfit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0
    for price in prices:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    return max_profit

48.2 多次交易

问题描述：与一次交易类似，但允许进行多次交易。

思路分析：这个问题可以视为对每一天都尝试做出最优的买卖决策，即如果今天的价格高于昨天，则视为昨天买入今天卖出（即使实际上并没有进行这样的操作，但逻辑上可以这样理解以增加利润）。由于允许多次交易，因此只需关注每一天相较于前一天的“增量”利润即可。

代码实现：

def maxProfit_kTransactions(prices):
    if not prices:
        return 0
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            max_profit += prices[i] - prices[i-1]
    return max_profit

48.3 含冷冻期的交易

问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。但是，你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。此外，卖出股票后，你无法在第二天买入股票（即冷冻期为1天）。

思路分析：这个问题在多次交易的基础上增加了冷冻期的限制。我们需要定义三个状态：dp[i][0]表示第i天不持有股票且处于冷冻期中的最大利润，dp[i][1]表示第i天持有股票的最大利润，dp[i][2]表示第i天不持有股票且不在冷冻期中的最大利润。根据状态定义，我们可以推导出状态转移方程。

代码实现（略去具体实现，因篇幅限制，但逻辑类似上述动态规划思路）：

需要为每一天计算三种状态下的最大利润，并考虑冷冻期的影响。

48.4 含交易费的交易

问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。此外，每次交易都需要支付一定的交易费。

思路分析：这个问题在多次交易的基础上增加了交易费用的考量。交易费用的存在使得简单的“低买高卖”策略不再总是最优解，因为每次交易都会扣除一定的费用。我们仍然可以采用动态规划的方法，但状态转移方程需要稍作调整，以考虑交易费用。

代码实现（同样略去具体实现，但思路是在多次交易的基础上，每次卖出时减去交易费用）：

需要修改状态转移方程，确保在计算卖出时的利润时扣除交易费用。

总结

股票买卖系列问题是一类极具代表性的动态规划问题，它们不仅考察了对动态规划思想的理解，还涉及到了状态定义、状态转移方程设计等多个关键步骤。通过本章节的学习，读者应该能够掌握解决这类问题的一般方法，并能够灵活应用到其他类似的场景中。同时，这些问题的解决过程也展示了算法设计中“分而治之”和“最优化”思想的应用，对于提升算法设计和问题解决能力大有裨益。