动态规划6：股票买卖问题

引言

在动态规划系列的前五篇文章中，我们分别学习了爬楼梯问题、最长公共子序列、01背包问题、最长递增子序列和不同路径问题。今天我们将探讨动态规划中极具实用价值的一类问题——股票买卖问题。

股票买卖问题是动态规划中的经典应用，它不仅在算法面试中频繁出现，更与实际的投资决策密切相关。通过学习这类问题，我们将深入理解状态机动态规划的设计思想和实现技巧。

问题背景

股票买卖问题的核心在于：在给定的股票价格序列中，通过买入和卖出操作获得最大利润。

这类问题通常具有以下特征：

• 时间序列：股票价格按时间顺序给出
• 操作限制：买入卖出有各种限制条件
• 状态转换：持有股票和不持有股票是两种不同的状态
• 最优化目标：追求最大利润

问题分类与解法

股票买卖问题根据交易限制可以分为几大类，我们将逐一分析：

类型一：买卖股票的最佳时机（只能交易一次）

LeetCode 121. 买卖股票的最佳时机

问题描述

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一天卖出该股票。设计一个算法来计算你所能获取的最大利润。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

解法一：暴力法

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            int profit = prices[j] - prices[i];
            maxProfit = Math.max(maxProfit, profit);
        }
    }
    return maxProfit;
}

时间复杂度：O(n²)，空间复杂度：O(1)

解法二：一次遍历（贪心思想）

核心思想：在每一天，我们都尝试以当前价格卖出，同时维护到目前为止的最低买入价格。

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;  // 更新最低买入价格
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;  // 更新最大利润
        }
    }
    
    return maxProfit;
}

时间复杂度：O(n)，空间复杂度：O(1)

解法三：动态规划（状态机思想）

状态定义：

• 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], -prices[i])              // 持有：保持持有 或 买入

代码实现：

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n <= 1) return 0;
    
    int[][] dp = new int[n][2];
    dp[0][0] = 0;           // 第0天不持有股票，利润为0
    dp[0][1] = -prices[0];  // 第0天持有股票，利润为-prices[0]
    
    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    }
    
    return dp[n-1][0];
}

空间优化版本：

public int maxProfit(int[] prices) {
    int sold = 0;           // 不持有股票的最大利润
    int hold = -prices[0];  // 持有股票的最大利润
    
    for (int i = 1; i < prices.length; i++) {
        sold = Math.max(sold, hold + prices[i]);
        hold = Math.max(hold, -prices[i]);
    }
    
    return sold;
}

类型二：买卖股票的最佳时机II（无限次交易）

LeetCode 122. 买卖股票的最佳时机 II

问题描述（无限次交易）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

示例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3。

解法一：贪心算法

核心思想：只要后一天的价格比前一天高，就进行交易。

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            maxProfit += prices[i] - prices[i-1];
        }
    }
    return maxProfit;
}

时间复杂度：O(n)，空间复杂度：O(1)

解法二：动态规划

状态转移方程：

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])  // 注意这里可以多次买入

public int maxProfit(int[] prices) {
    int sold = 0;
    int hold = -prices[0];
    
    for (int i = 1; i < prices.length; i++) {
        int newSold = Math.max(sold, hold + prices[i]);
        int newHold = Math.max(hold, sold - prices[i]);
        sold = newSold;
        hold = newHold;
    }
    
    return sold;
}

类型三：买卖股票的最佳时机III（最多2次交易）

LeetCode 123. 买卖股票的最佳时机 III

问题描述（最多2次交易）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

解法：动态规划

状态定义：

• buy1：第一次买入后的最大利润
• sell1：第一次卖出后的最大利润
• buy2：第二次买入后的最大利润
• sell2：第二次卖出后的最大利润

public int maxProfit(int[] prices) {
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    
    for (int i = 1; i < prices.length; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    
    return sell2;
}

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

LeetCode 188. 买卖股票的最佳时机 IV

问题描述（最多k次交易）

给定一个整数数组 prices 和一个整数 k，其中 prices[i] 是第 i 天的股票价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

解法：动态规划（k次交易）

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n <= 1 || k == 0) return 0;
    
    // 如果k足够大，相当于无限次交易
    if (k >= n / 2) {
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1]) {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
    
    // dp[i][j] 表示第i天最多j次交易的最大利润
    // 0表示不持有股票，1表示持有股票
    int[][][] dp = new int[n][k+1][2];
    
    // 初始化第一天的状态
    for (int j = 1; j <= k; j++) {
        dp[0][j][0] = 0;
        dp[0][j][1] = -prices[0];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            // 不持有股票：保持不持有 或 卖出
            dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
            // 持有股票：保持持有 或 买入（交易次数-1）
            dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
        }
    }
    
    return dp[n-1][k][0];
}

类型五：买卖股票的最佳时机含冷冻期

LeetCode 309. 买卖股票的最佳时机含冷冻期

问题描述（含冷冻期）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）：

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
• 卖出股票后，你无法在第二天买入股票（即冷冻期为1天）

解法：动态规划（含冷冻期）

状态定义：

• hold：持有股票的最大利润
• sold：刚卖出股票的最大利润（处于冷冻期）
• rest：不持有股票且不在冷冻期的最大利润

public int maxProfit(int[] prices) {
    if (prices.length <= 1) return 0;
    
    int hold = -prices[0];  // 持有股票
    int sold = 0;           // 刚卖出（冷冻期）
    int rest = 0;           // 不持有且不在冷冻期
    
    for (int i = 1; i < prices.length; i++) {
        int prevHold = hold;
        int prevSold = sold;
        int prevRest = rest;
        
        hold = Math.max(prevHold, prevRest - prices[i]);  // 持有：保持 或 从rest买入
        sold = prevHold + prices[i];                      // 卖出：从hold卖出
        rest = Math.max(prevRest, prevSold);              // 休息：保持 或 从sold恢复
    }
    
    return Math.max(sold, rest);
}

通用解法框架

通过分析上述问题，我们可以总结出股票买卖问题的通用解法框架：

状态机设计

状态定义：dp[i][k][s]
- i：第i天
- k：最多k次交易
- s：当前状态（0=不持有，1=持有）

状态转移：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])    // 卖出
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) // 买入

边界条件处理

base case:
dp[0][k][0] = 0          // 第0天不持有股票，利润为0
dp[0][k][1] = -prices[0] // 第0天持有股票，利润为-prices[0]

空间优化策略

由于状态只依赖于前一天，通常可以将空间复杂度从 O(nk) 优化到 O(k)。

解题技巧总结

1. 问题转化

• 将复杂的交易限制转化为状态机
• 明确每个状态的含义和转移条件

2. 特殊情况优化

• 当 k ≥ n/2 时，相当于无限次交易
• 对于冷冻期，增加中间状态处理

3. 空间优化

• 滚动数组优化空间复杂度
• 状态压缩减少维度

实际应用价值

股票买卖问题不仅是算法问题，还具有重要的实际应用价值：

1. 投资策略分析

• 帮助理解不同交易策略的收益上限
• 为量化交易提供理论基础

2. 算法思维训练

• 状态机设计思想
• 动态规划的实际应用

3. 面试准备

• 高频面试题目
• 考察多种算法思维

复杂度分析

问题类型	时间复杂度	空间复杂度	主要思想
买卖一次	O(n)	O(1)	贪心/DP
无限次交易	O(n)	O(1)	贪心
最多k次	O(nk)	O(k)	DP
含冷冻期	O(n)	O(1)	状态机DP

总结

股票买卖问题是动态规划中的经典应用，它完美地展现了状态机动态规划的设计思想：

1. 状态设计巧妙：通过持有/不持有股票来划分状态
2. 转移逻辑清晰：买入、卖出、持有三种操作对应不同的状态转移
3. 优化策略多样：从暴力到DP，从二维到一维的优化过程
4. 实用价值高：既是算法问题，又有实际应用意义

通过掌握股票买卖问题的解法，我们不仅学会了具体的算法技巧，更重要的是理解了如何将现实问题抽象为状态机，如何设计状态和转移方程。

系列文章回顾

• 动态规划入门：从爬楼梯问题开始
• 动态规划进阶：最长公共子序列问题
• 动态规划深入：01背包问题详解
• 动态规划4：最长递增子序列问题
• 动态规划5：不同路径问题与路径计数

推荐练习

• 在LeetCode上练习股票买卖相关的所有题目
• 尝试实现通用的股票买卖问题求解框架
• 思考其他具有状态机特征的动态规划问题