每日算法 — 使用java实现买卖股票：动态规划状态机与最大利润决策

问题背景

股票交易是投资领域最经典的决策问题之一。假设给定一段时间内某只股票每天的价格，你最多可以完成若干笔交易，如何在遵守交易规则的前提下获取最大利润？这一问题不仅具有实际意义，更是动态规划与状态机设计的经典教学案例。

本文将从最简单的单交易限制出发，逐步扩展到无限制交易、含冷冻期、含手续费等多种变体，用Java完整实现各类买卖股票问题的最优解法。

问题描述与变体

基础问题（LeetCode 121）

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你只能选择某一天买入，并在未来的某一天卖出，求能获取的最大利润。

扩展变体

• 多次交易（LeetCode 122）：可以进行多次买卖，但同一时间只能持有一支股票
• 最多两笔交易（LeetCode 123）：最多完成两笔交易
• k次交易限制（LeetCode 188）：最多完成k笔交易
• 含冷冻期（LeetCode 309）：卖出后有一天冷冻期不能买入
• 含手续费（LeetCode 714）：每笔交易需支付手续费

核心思路：状态机设计

买卖股票问题的核心在于用状态机刻画每一天结束后投资者的持仓状态：

• 状态0（持有股票）：当天结束时手中持有一支股票
• 状态1（未持有股票）：当天结束时手中没有股票

每天的状态只能从前一天的状态转移而来，转移规则如下：

Java完整实现

import java.util.Arrays;

/**
 * 买卖股票系列问题的完整Java实现
 * 涵盖单交易、多次交易、K次交易、冷冻期、手续费等变体
 */
public class StockTrading {

    /**
     * 121. 买卖股票的最佳时机 - 只能交易一次
     * 思路：记录历史最低价格，每天计算当天卖出的最大利润
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxProfitOneTransaction(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPrice = prices[0];  // 历史最低买入价格
        int maxProfit = 0;         // 当前最大利润

        for (int i = 1; i < prices.length; i++) {
            // 更新历史最低价格
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            // 计算当天卖出的利润，更新最大利润
            int profit = prices[i] - minPrice;
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }

        return maxProfit;
    }

    /**
     * 122. 买卖股票的最佳时机II - 可以多次交易
     * 思路：贪心策略，所有上涨区间都参与
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxProfitUnlimited(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int totalProfit = 0;
        // 只要今天比昨天贵，就昨天买今天卖
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                totalProfit += diff;
            }
        }

        return totalProfit;
    }

    /**
     * 122. 买卖股票的最佳时机II - 动态规划版本
     * 状态机设计：dp[i][0]持有，dp[i][1]未持有
     */
    public int maxProfitUnlimitedDP(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int n = prices.length;
        // hold: 当天持有股票的最大利润
        // notHold: 当天未持有股票的最大利润
        int hold = -prices[0];
        int notHold = 0;

        for (int i = 1; i < n; i++) {
            int newHold = Math.max(hold, notHold - prices[i]);
            int newNotHold = Math.max(notHold, hold + prices[i]);
            hold = newHold;
            notHold = newNotHold;
        }

        // 最终未持有股票的状态利润更大
        return notHold;
    }

    /**
     * 123. 买卖股票的最佳时机III - 最多两笔交易
     * 状态机扩展：定义四个状态
     * firstBuy: 第一次买入后的最大利润
     * firstSell: 第一次卖出后的最大利润
     * secondBuy: 第二次买入后的最大利润
     * secondSell: 第二次卖出后的最大利润
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxProfitTwoTransactions(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        // 初始状态：买入后利润为-price，未买入为0
        int firstBuy = -prices[0];
        int firstSell = 0;
        int secondBuy = -prices[0];  // 可以理解为先买入再卖出再买入
        int secondSell = 0;

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            // 按依赖顺序更新：后续状态依赖前序状态的前一轮值
            // 使用临时变量避免覆盖
            int newFirstBuy = Math.max(firstBuy, -price);
            int newFirstSell = Math.max(firstSell, firstBuy + price);
            int newSecondBuy = Math.max(secondBuy, firstSell - price);
            int newSecondSell = Math.max(secondSell, secondBuy + price);

            firstBuy = newFirstBuy;
            firstSell = newFirstSell;
            secondBuy = newSecondBuy;
            secondSell = newSecondSell;
        }

        return secondSell;
    }

    /**
     * 188. 买卖股票的最佳时机IV - 最多k笔交易
     * 通用动态规划：dp[i][k][0/1]表示第i天最多k笔交易，持有/未持有的最大利润
     * 空间优化后只需要两个一维数组
     * 时间复杂度：O(n*k)  空间复杂度：O(k)
     */
    public int maxProfitKTransactions(int k, int[] prices) {
        if (prices == null || prices.length < 2 || k == 0) {
            return 0;
        }

        // 关键优化：如果k超过n/2，等价于无限次交易
        int n = prices.length;
        if (k >= n / 2) {
            return maxProfitUnlimited(prices);
        }

        // buy[j]: 第j笔交易买入后的最大利润
        // sell[j]: 第j笔交易卖出后的最大利润
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];

        // 初始化：所有买入状态为负无穷（未发生）
        Arrays.fill(buy, Integer.MIN_VALUE);
        buy[0] = -prices[0];  // 第一笔买入

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                // 更新第j笔交易的卖出状态
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
                // 更新第j笔交易的买入状态（从第j-1笔卖出的状态转移）
                buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
            }
            // 第0笔买入也要更新（第一次买入）
            buy[0] = Math.max(buy[0], -prices[i]);
        }

        int maxProfit = 0;
        for (int j = 0; j <= k; j++) {
            maxProfit = Math.max(maxProfit, sell[j]);
        }
        return maxProfit;
    }

    /**
     * 309. 最佳买卖股票时机含冷冻期 - 卖出后一天不能买入
     * 三个状态：持有、未持有（冷冻期）、未持有（可买入）
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxProfitWithCooldown(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int n = prices.length;
        // hold: 持有股票
        // notHoldCanBuy: 未持有，且可以买入（前一天没有卖出）
        // notHoldCooldown: 未持有，但处于冷冻期（前一天刚卖出）
        int hold = -prices[0];
        int notHoldCanBuy = 0;
        int notHoldCooldown = Integer.MIN_VALUE;  // 第一天不可能处于冷冻期

        for (int i = 1; i < n; i++) {
            int newHold = Math.max(hold, notHoldCanBuy - prices[i]);
            int newNotHoldCanBuy = Math.max(notHoldCanBuy, notHoldCooldown);
            int newNotHoldCooldown = hold + prices[i];  // 今天卖出，明天冷冻

            hold = newHold;
            notHoldCanBuy = newNotHoldCanBuy;
            notHoldCooldown = newNotHoldCooldown;
        }

        return Math.max(notHoldCanBuy, notHoldCooldown);
    }

    /**
     * 714. 买卖股票的最佳时机含手续费 - 每笔卖出需付手续费
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxProfitWithFee(int[] prices, int fee) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int hold = -prices[0];  // 持有股票
        int notHold = 0;         // 未持有股票

        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, notHold - prices[i]);
            // 卖出时扣除手续费
            int newNotHold = Math.max(notHold, hold + prices[i] - fee);
            hold = newHold;
            notHold = newNotHold;
        }

        return notHold;
    }

    // ============ 测试入口 ============
    public static void main(String[] args) {
        StockTrading solution = new StockTrading();

        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("价格序列: " + Arrays.toString(prices));
        System.out.println("单交易最大利润: " + solution.maxProfitOneTransaction(prices));
        System.out.println("无限交易最大利润: " + solution.maxProfitUnlimited(prices));
        System.out.println("无限交易DP版本: " + solution.maxProfitUnlimitedDP(prices));
        System.out.println("最多两笔交易: " + solution.maxProfitTwoTransactions(prices));
        System.out.println("最多3笔交易: " + solution.maxProfitKTransactions(3, prices));
        System.out.println("含冷冻期: " + solution.maxProfitWithCooldown(prices));
        System.out.println("含手续费(2): " + solution.maxProfitWithFee(prices, 2));

        System.out.println("\n--- 冷冻期测试 ---");
        int[] prices2 = {1, 2, 3, 0, 2};
        System.out.println("价格序列: " + Arrays.toString(prices2));
        System.out.println("含冷冻期: " + solution.maxProfitWithCooldown(prices2));
    }
}

复杂度分析

关键技巧总结

1. 状态机抽象：将交易过程抽象为有限状态（持有/未持有），通过状态转移方程统一解决各类变体
2. 空间压缩：由于每天状态只依赖前一天，可将二维DP压缩为一维，甚至O(1)空间
3. 贪心剪枝：当交易次数k超过n/2时，问题退化为无限交易，可用贪心O(n)解决
4. 边界处理：注意初始状态的正确设置，未发生交易时利润为负无穷而非零

扩展思考

• 如何加入涨跌停限制？需要在状态转移时加入价格约束
• 如何同时考虑多只股票？需要增加股票维度的状态
• 如何建模融资融券（允许做空）？增加卖出后持有负股的状态