算法：买卖股票系列

Leetcode 上有一个买卖股票系列的算法问题，主要区别在于是否有交易次数限制、是否交易有冷却期、是否有交易手续费等条件。本文探究的就是这个系列的通用思路和解法、不同条件时的修改以及最优解。阅读本文需要事先对这个系列各个问题的题目有一定的了解，了解 动态规划。本文会从最复杂的条件开始，得出最通用的解法，所以一开始反而是最难的，推荐有兴趣、有耐心的读者先从头到尾阅读一遍，如果难以理解的话，再从最简单的条件开始阅读，这样就可以深刻了解这个系列的解题思路，掌握解题模板。本文代码使用的语言是 Java。

核心思路

定义一个二维数组 int[][] profit = new int[n][2] ，其中 profit[i][0] 表示第 i 天卖出股票(没有持有股票)时的最大收益，profit[i][1] 表示表示第 i 天买入股票(持有股票)时的最大收益

那么状态转移方程是：

// 第i天的卖出状态 = Max(前一天卖出状态，前一天买入状态 + 卖出股票获得的收益)
profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
// 第i天的买入状态 = Max(前一天买入状态，前一天前一次已卖出状态 - 买入股票扣除的收益)
profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);

这个系列所有问题的解答都是基于这个状态转移方程

通用的解法

首先得出考虑了 Leetcode 上买卖股票系列所有不同条件下的通用解

// k表示交易次数，fee表示交易手续费，m表示交易冷却期
public int maxProfit(int k, int[] prices, int fee, int m) {
    if (k == 0 || prices == null || prices.length < 2) {
        return 0;
    }
    int n = prices.length;
    
    // 进行一次完全的交易需要两天，所以当 k > n/2 的时候，就可以每天都进行一次买入（卖出）操作，也就是可以交易无数次
    if (k > (n >> 1)) {
        int[][] profit = new int[n][2];
        for (int i = 0; i < n; i++) {
            // 处理初始状态
            if (i == 0) {
                profit[i][0] = 0;
                profit[i][1] = -prices[0];
                continue;
            }
            // 处理有交易冷却期时，前 m + 1 天的情况，由于这时候不能卖出，所以前一天卖出状态的最大收益都为0
            if (i < m + 1) {
                profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i] - fee);
                profit[i][1] = Math.max(profit[i - 1][1], 0 - prices[i]);
                continue;
            }
            // 核心，状态转移方程
            profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i] - fee);
            profit[i][1] = Math.max(profit[i - 1][1], profit[i - (m + 1)][0] - prices[i]);
            
        }
        return profit[n - 1][0];
    }
    
    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            // 处理初始状态
            if (i == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            // 处理有交易冷却期时，前 m + 1 天的情况，由于这时候不能卖出，所以前一天卖出状态的最大收益都为0
            if (i < m + 1) {
                profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i] - fee);
                profit[i][j][1] = Math.max(profit[i - 1][j][1], 0 - prices[i]);
                continue;
                
            }
            // 核心，状态转移方程
            profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i] - fee);
            profit[i][j][1] = Math.max(profit[i - 1][j][1], profit[i - (m + 1)][j - 1][0] - prices[i]);
        }
    }
    return profit[n - 1][k][0];
}

从上面函数可以看出，i 表示的天数这一维度可以省略，但如果有交易冷却期这个条件的话，需要额外添加一个数组来保存 i - (m + 1) 天前的值，优化后的代码如下

public int maxProfit(int k, int[] prices, int fee, int m) {
    if (k == 0 || prices == null || prices.length < 2) {
        return 0;
    }
    
    int n = prices.length;

    if (k > (n >> 1)) {
        int sell = 0;
        int buy = Integer.MIN_VALUE + fee;
        // 保存 i - (m + 1) 天前的值
        int[] preSells = new int[m + 1];
        for (int i = 0; i < prices.length; i++) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, preSells[i % (m + 1)] - prices[i]);
            preSells[i % (m + 1)] = sell;
        }
        return sell;
    }
    
    int[] sells = new int[k];
    int[] buys = new int[k];
    // 保存 i - (m + 1) 天前的值
    int[][] preSells = new int[k][m + 1];
    
    // 处理初始状态
    for (int i = 0; i < k; i++) {
        sells[i] = 0;
        buys[i]=  Integer.MIN_VALUE + fee;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (j == 0) {
                sells[j] = Math.max(sells[j], buys[j] + prices[i] - fee);
                buys[j] = Math.max(buys[j], -prices[i]);
                preSells[j][i % (m + 1)] = sells[j];
                continue;
            }
            sells[j] = Math.max(sells[j], buys[j] + prices[i] - fee);
            buys[j] = Math.max(buys[j], preSells[j - 1][i % (m + 1)] - prices[i]);
            preSells[j][i % (m + 1)] = sells[j];
        }
    }
    return sells[k - 1];
}

这个系列所有问题都可以在上面的代码基础上进行修改优化，去除不必要的代码即可得出解

应用

利用以上的通用解，解决 Leetcode 的具体题目，从最困难的题目开始到最简单的题目，由深到浅地理解通用解的每一行代码。

只能交易 k 次

Leetcode 的 188 题

由于只有一个交易次数的条件，所以不需要 m ，也不需要 fee ，直接简化代码即可

public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices == null || prices.length < 2) {
         return 0;
    }
    
    int n = prices.length;

    // 进行一次完全的交易需要两天，所以当 k > n/2 的时候，就可以每天都进行一次买入（卖出）操作，也就是可以交易无数次
    if (k > (n >> 1)) {
        int[][] profit = new int[n][2];

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                profit[i][0] = 0;
                profit[i][1] = -prices[0];
                continue;
            }
            profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
            profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
        }
        return profit[n - 1][0];
    }

    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            if (i == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i]);
            profit[i][j][1] = Math.max(profit[i - 1][j][1], profit[i - 1][j - 1][0] - prices[i]);
        }
    }
    return profit[n - 1][k][0];
}

优化

public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices == null || prices.length < 2) {
        return 0;
    }

    int n = prices.length;

    if (k > (n >> 1)) {
        int sell = 0;
        int buy = Integer.MIN_VALUE;
        for (int price : prices) {
            sell = Math.max(sell, buy + price);
            buy = Math.max(buy, sell - price);
        }
        return sell;
    }

    int[] sells = new int[k];
    int[] buys = new int[k];

    for (int i = 0; i < k; i++) {
        sells[i] = 0;
        buys[i]=  Integer.MIN_VALUE;
    }

    for (int price : prices) {
        for (int i = 0; i < k; i++) {
            if (i == 0) {
                sells[i] = Math.max(sells[i], buys[i] + price);
                buys[i] = Math.max(buys[i], -price);
                continue;
            }
            sells[i] = Math.max(sells[i], buys[i] + price);
            buys[i] = Math.max(buys[i], sells[i - 1] - price);
        }
    }
    return sells[k - 1];
}

只能交易两次

Leetcode 的 123 题

由于只有一个交易次数的条件，所以不需要 m ，也不需要 fee ，直接简化代码得

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    int k = 2;
    int n = prices.length;

    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            if (i == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }

            profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i]);
            profit[i][j][1] = Math.max(profit[i - 1][j][1], profit[i - 1][j - 1][0] - prices[i]);
        }
    }

    return profit[n - 1][k][0];
}

优化，由于只能交易两次，所以只需要两组变量来保存结果即可

public int maxProfit(int[] prices) {
    int sell1 = 0;
    int buy1 = Integer.MIN_VALUE;
    int sell2 = 0;
    int buy2 = Integer.MIN_VALUE;

    for (int price : prices) {
        sell1 = Math.max(sell1, buy1 + price);
        buy1 = Math.max(buy1, -price);
        sell2 = Math.max(sell2, buy2 + price);
        buy2 = Math.max(buy2, sell1 - price);
    }
    return sell2;
}

只能交易一次

Leetcode 的 121 题

由于只有一个交易次数的条件，所以不需要 m ，也不需要 fee ；同时因为只能交易一次，所以 k = 1 ，也就是可以省略

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    int n = prices.length;
    int[][] profit = new int[n][2];

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        // 因为只能交易一次，所以这里的 profit[i - 1][0] 恒等于 0
        profit[i][1] = Math.max(profit[i - 1][1], -prices[i]);
    }
    return profit[n - 1][0];
}

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    for (int price : prices) {
        sell = Math.max(sell, buy + price);
        buy = Math.max(buy, -price);
    }

    return sell;
}

这个题目有更通俗直接的解法

// 遍历的同时，保存数组中的最小值，更新最大差值
public int maxProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for (int price : prices) {
        if (price < min) {
            min = price;
        } else if (price - min > profit) {
            profit = price - min;
        }
    }
    return profit;
}

可以交易无数次

Leetcode 的 122 题

由于只一个交易次数的条件，所以不需要 m ，也不需要 fee ；至于 k 这一维度，也可以删除，有两种理解方式

可以交易无数次，也就是 k = +∞ ，这时候 k ≈ k - 1 ，所以 k 可以认为是没有作用的，可以删除 k 这一维度
之前需要 k 这一维度是因为有交易次数限制，每天都要进行遍历，从 k 次交易内选择最优方案；但如果没有交易次数限制，则可以认为每天都进行交易，收益可以一直累加，下一天直接取之前的最优方案即可，所以可以删除 k 这一维度

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    int n = prices.length;
    int[][] profit = new int[n][2];


    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        // 这里的 profit[i - 1][0] 表示前一天的最优方案，因为没有交易次数限制，也就是收益可以一直累加
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[n - 1][0];
}

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    for (int price : prices) {
        sell = Math.max(sell, buy + price);
        buy = Math.max(buy, sell - price);
    }
    return sell;
}

可以看出只能交易一次与可以交易无数次的区别：

只能交易一次：前一天的收益恒为 0
可以交易无数次：收益可以一直累加

更通俗直接的解法，贪心算法

// 由于不限交易次数，所以只要后面的价格比较大，都能获得收益
public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        int today = prices[i];
        int tomorrow = prices[i + 1];
        if (today < tomorrow) {
            maxProfit += tomorrow - today; 
        }
    }
    return maxProfit;
}

可以交易无数次，有一天的冷却期

Leetcode 的 309 题

在可以交易无数次的条件上，加上 m 这个条件即可

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    // 如果冷却期是 n 天的话，让 m = n 即可
    int m = 1;
    int n = prices.length;
    int[][] profit = new int[n][2];


    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        if (i < m + 1) {
            profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
            profit[i][1] = Math.max(profit[i - 1][1], 0 - prices[i]);
            continue;
        }
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - (m + 1)][0] - prices[i]);
    }
    return profit[n - 1][0];
}

优化

public int maxProfit(int[] prices) {
    // 如果冷却期是 n 天的话，让 m = n 即可
    int m = 1;
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    int[] preSells = new int[m + 1];
    for (int i = 0; i < prices.length; i++) {
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, preSells[i % (m + 1)] - prices[i]);
        preSells[i % (m + 1)] = sell;
    }
    return sell;
}

可以交易无数次，无冷却期，有手续费

Leetcode 的 714 题

在可以交易无数次的条件上，加上 fee 这个条件即可

public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    int n = prices.length;
    int[][] profit = new int [n][2];
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i] - fee);
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[n - 1][0];
}

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    // 以防溢出
    int buy = Integer.MIN_VALUE + fee;
    for (int price : prices) {
        sell = Math.max(sell, buy + price - fee);
        buy = Math.max(buy, sell - price);
    }
    return sell;
}

总结

从最困难的题目开始入手这个系列解法或许有点令人难以接受，但这反而是我个人认为最能全局深刻理解掌握这个系列的办法，最复杂的情况都解决了，剩下的就会变得越来越简单。我推荐先从头到尾认真阅读一次，有个全局的印象，再从尾到头阅读一次，理解当条件越来越复杂的时候，代码是怎么改变的，怎么兼容的。相信各位读者看完以上这么多不同条件下的解法以及优化后的代码，一定会对 动态规划 有更深的理解，如果有更优的解法，欢迎一起探讨。

最后编辑于：2020.07.02 15:55:47

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,681评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,710评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,623评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,202评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,232评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,368评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,795评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,461评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,647评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,476评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,525评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,226评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,785评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,857评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,090评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,647评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,215评论 2赞 341