阅读 86

股票问题汇总

导言

股票买卖问题是 LeetCode 算法题当中的一个系列问题,主要的考查点就是动态规划,但是如果针对这里的每道题都去思考和总结,其实得到的解法不具有一般性,这篇文章想要做的就是针对这一系列问题提炼出一个通用解法


题目概览

股票买卖这一类的问题,都是给一个输入数组,表示的是每天的股价,并且限定你手头不能存有多于 1 支股,也就是手上有股票的时候必须卖掉才能再继续卖,而且只能买一支,一般来说有下面几种问法:

  • 只能买卖一次
  • 可以买卖无数次
  • 可以买卖 k 次

当然还有一些变种,例如每次买卖都有交易费,另外还有就是交易过后必需隔一天再继续买卖。


解题思路

这类题目当中的头两题,就是只能交易一次,和可以交易无数次是可以根据常识来解决的,只能交易一次无非就是遍历数组记录当前经过的最小值,然后用当前值减去最小值去记录差价,去差价最大的即可。只能交易无数次也是遍历数组,只要当前的值 比之前的存在的值大,就累加差价,并且把当前遍历到的值设置成 “之前的值”,然后继续遍历下去。

这里主要考虑 k 次交易的情况,当然这里的框架稍作调整也是可以用到只能交易一次和可以交易无数次的题目中去的,最好的解决方式肯定是动态规划,但是关键在于状态怎么定义,动态规划的方程怎么写。我们可以思考得出题目当中的变量有以下几个:

  • 第几天
  • 股票的价格
  • 当前可获得的最大利润
  • 手头有无股票
  • 第几次交易

其中 “当前可获得的最大利润” 就是我们最后要求解的值,那么这么看来 DP 数组的值可以试着用来表示 “当前可获得的最大利润” ,然后接着看,由于给定了输入数组,“股票的价格” 是和 “第几天” 绑定在一起的,这样 DP 的状态其实是由 “第几天”,“手头有无股票”,还有 “第几次交易” 来决定的,那我们就可以得到 DP 的状态:

DP[i][j][0] -> 第 i 天,第 j 次交易,手头没有股票的最大利润
DP[i][j][1] -> 第 i 天,第 j 次交易,手头有股票的最大利润
复制代码

这样,我们要求解的答案就是:

Max(DP[n][0][0], DP[n][1][0], ..., DP[n][k][0])
复制代码

这里补充一点就是,手头有股票的情况肯定不会是最后的答案,因为股票的价格都是正数,买股票是要花钱的,即 DP[i][j][0] - prices[a] < DP[i][j][0]

另外一个问题就是动归的递推方程怎么写,因为当前的 DP 状态只会和它之前的状态相关,并不会被后面的状态所影响,而且在思考的过程中要有一个认识就是,之前的 DP 值全是局部的最优解,因此,我们可以思考一个问题是 “当前的最大利润和前面哪些状态相关?”,然后你会发现每个状态只会和它相邻的状态影响,也就是第 i 天的最大利润可以通过第 i - 1 天的最大利润求解,第 k 次交易的最大利润可以通过第 k - 1 次交易的最大利润求解,另外就是手头有无股票也是可以通过买入和卖出相互转化的,因此我们可以得出递推方程如下:

DP[i][k][0] = Max(DP[i - 1][k][0], DP[i - 1][k - 1][1] + a[i])
DP[i][k][1] = Max(DP[i - 1][k][1], DP[i - 1][k - 1][0] - a[i])
复制代码

有了 DP 的状态定义,和递推方程,剩下的工作就是写代码了,应该问题已经基本解决了。


参考代码

LeetCode 121. Best Time to Buy and Sell Stock

这道题比较简单,套进我们之前总结解法也是可以很好解决的,k = 1,这里 DP 数组开 2 是为了来表示没有交易和交易 1 次:

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    
    int[][][] dp = new int[prices.length][2][2];
    
    dp[0][0][0] = 0; dp[0][0][1] = -prices[0];
    
    for (int i = 1; i < prices.length; ++i) {
        dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][0][1] + prices[i]);
        dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
    }
    
    return dp[prices.length - 1][1][0];
}
复制代码

LeetCode 122. Best Time to Buy and Sell Stock II

因为这题的交易次数不受限制,也就是当前进行买和卖都是可以的,不用考虑前面的 k - 1 次的状态,因此我们就不必开多一维数组

public int maxProfit(int[] prices) {
    if ((prices == null) || (prices.length < 2)) {
        return 0;
    }
    
    int[][] dp = new int[prices.length][2];
    
    dp[0][0] = 0; dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++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], dp[i - 1][0] - prices[i]);
    }
    
    return dp[prices.length - 1][0];
}
复制代码

LeetCode 123. Best Time to Buy and Sell Stock III

这道题符合我们之前讲到的框架,其中 k = 2,因此根据 DP 状态中的交易次数,我们开长度为 3 的 DP 数组,分别用来表示第 0 次交易,第 1 次交易,第 2 次交易,其中 dp[i][0][0] 是不用根据前面的状态来更新的,其值永远等于零,即 dp[0][0][0] = dp[1][0][0] = ... = dp[n - 1][0][0],还有 dp[i][2][1] 也是不需要考虑的,因为交易次数限定为最高 2 次,不可能存在第三次交易的情况

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    
    // dp[i][j][k] -> day, time, whether have stock or not
    int[][][] dp = new int[prices.length][3][2];
    
    dp[0][0][1] = -prices[0]; dp[0][1][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
        dp[i][0][1] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][0][1]);

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

        dp[i][2][0] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][2][0]);
    }
    
    return dp[prices.length - 1][2][0];
}
复制代码

LeetCode 188. Best Time to Buy and Sell Stock IV

这题就是我们之前讨论当中的案例,但是考虑到第 0 次交易的情况是没法根据前面的 DP 的值来计算的,为来计算的方便,把第 0 次交易的情况单独挪出第二层循环进行处理,还有就是,LeetCode 给了一个非常极端的 testcase,就是 k 非常大,k >> prices.length,为了程序能够顺利通过,这种情况下就直接变成第二题的解法,这里就直接按常识简写了:

public int maxProfit(int k, int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    
    if (k > prices.length / 2) {
        int max = 0; int hold = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            max += Math.max(0, prices[i] - prices[i - 1]);
        }
        
        return max;
    }
    
    // dp[i][j][0] -> at ith day, jth transaction, without stock in hand
    // dp[i][j][1] -> at ith day, jth transaction, with stock in hand
    int[][][] dp = new int[prices.length][k + 1][2];
    
    // init
    for (int i = 0; i <= k; ++i) {
        dp[0][i][1] = -prices[0];
    }
    
    for (int i = 1; i < prices.length; ++i) {
        dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
        for (int j = 1; j <= k; ++j) {
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);
            dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);
        }
    }
    
    return dp[prices.length - 1][k][0];
}
复制代码

LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

这道题在买卖不受限制题目的基础上,加了条件,就是买卖后,必须等上至少一天才能继续买卖,这样的话状态略微改变即可,就是在之前 “手头有股票” 和 “手头没有股票” 两种状态的基础上,多加一个 “冷却” 这么一个状态;递推方程跟之前不同的是,买股票的话,只能从前一天的 “冷却” 状态来决定,而不是 “手头没有股票”

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    
    int[][] dp = new int[prices.length][3];
    
    dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0;
    
    for (int i = 1; i < prices.length; ++i) {
        dp[i][0] = Math.max(dp[i - 1][1] + prices[i], Math.max(dp[i - 1][0], dp[i - 1][2]));
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][2]);
    }
    
    return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
}
复制代码

LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

这道题也是在买卖不受限制题目的基础上加上了 “每次交易都要交费用,每次费用相同” 这么一个条件,那其实在买卖不受限制题目的基础上,唯一需要改变的就是在卖票的时候减去交易费用即可,当然在买股票的时候减去这个交易费也是可以的

public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    
    int[][] dp = new int[prices.length][2];
    
    dp[0][0] = 0; dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    
    return dp[prices.length - 1][0];
}
复制代码

总结

以上六道题就是 LeetCode 当中股票系列的全部内容,当然这样的设定 DP 状态和定义 DP 递推方程的思想,是可以复用到其他类型的 DP 问题当中去的,总的来说就是根据变量来定义 DP 数组当中存的值以及状态,根据当前状态和之前状态的关系来确定 DP 方程,这个需要平时的积累和大量的刷题练习。另外题目解答当中没有提到的是,对于 DP 数组的空间优化,我们可以利用滚动数组来优化。

关注下面的标签,发现更多相似文章
评论