[Leetcode] 股票买卖问题总结

yPhantom 2020年02月06日 29次浏览

本篇文章主要针对以下问题:

  1. 121. Best Time to Buy and Sell Stock
  2. 122. Best Time to Buy and Sell Stock II
  3. 123. Best Time to Buy and Sell Stock III
  4. 188. Best Time to Buy and Sell Stock IV
  5. 309. Best Time to Buy and Sell Stock with Cooldown
  6. 714. Best Time to Buy and Sell Stock with Transaction Fee

总结一个框架模板,来解决所有类似问题。每个问题可能会存在效率更高更简洁的方法,但并不在本篇文章讨论范围之内。

对于这些问题的模板分析在Leetcode的讨论区已经有很好的回答(见文末),我就不再复述一遍的,这里仅仅记录一些自己的想法。


这六道题都可以用动态规划的方法来解决。其中最基础适用性最广的解答方法出自188. Best Time to Buy and Sell Stock IV这道hard难度的题目,其他五道题都可以直接套用188题的解法,做一些化简即可。

动态规划的解法,其核心是状态。在之后做其他题目时,一定要注意状态这个东西。

在买卖股票问题中,存在哪些状态呢?三种,时间,买卖几次以及是否持有股票。

当然这是我在已经充分分析并解决这些问题之后,能够十分明确的指出这三种状态,如果突然碰到一道题就能分析出其状态来使用动态规划,这应该是需要大量的练习的。

我们一般在做题目的时候,常常会这么写:

for 状态1 in ...
    for 状态2 in ...
        for 状态3 in ...
            dp[状态1][状态2][状态3] = 择优(选择1, 选择2)

那么针对股票买卖,我们这样定状态:

dp[i][k][0] : 第i天交易k次并且未持有股票的最大利润
dp[i][k][1] : 第i天交易k次并且持有股票的最大利润

因此有

 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])
 今天持有            昨天持有               昨天未持有,今天买了

这里呢,我们让k的变化发生买入股票的时候,实际上放在卖出那也可以。当我们卖出股票时+prices[i],当我们买入股票时-prices[i]。比如我们买的时候股价是1,卖的时候股价是6。那么就是+6 - 1 = 5了。


121. Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        for (int i = 1; i <= prices.length; i++) {
            if (i == 1) {
                dp[i][1] = -prices[i - 1];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = Math.max(-prices[i - 1], dp[i - 1][1]); 
        }
        return dp[prices.length][0];
    }
}

一道easy题,只能交易一次,k可以直接化简掉。注意i = 1时的判断。

122. Best Time to Buy and Sell Stock II

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        for (int i = 1; i < prices.length + 1; i++) {
            if (i == 1) {
                dp[i][1] = -prices[i - 1];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

122题k无限次,也可以直接化简掉。122题与121题的唯一差别在于交易1次和交易无限次。和代码差别在于求dp[i][1]的时候,121题的“昨天未持时”的利润一定是0,而122题由于可以交易无限次,那么之前的利润不一定为0。这与0/1背包问题、完全背包的思想是一样的。

123. Best Time to Buy and Sell Stock III

class Solution {
    public int maxProfit(int[] prices) {
        int k = 2;
        int[][][] dp = new int[prices.length + 1][k + 1][2];
        for (int i = 1; i <= prices.length; i++) {
            for (int j = k; j >= 1; j--) {
                if (i == 1) {
                    dp[i][j][1] = -prices[0];
                    continue;
                }
                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 - 1]);
            }
        }
        return dp[prices.length][k][0];
    }
}

这里k为2。

188. Best Time to Buy and Sell Stock IV

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k > prices.length / 2) {
            return maxProfit2(prices); // 使用无限次交易
        }
        int[][][] dp = new int[prices.length + 1][k + 1][2];
        for (int i = 1; i <= prices.length; i++) {
            for (int j = k; j >= 1; j--) {
                if (i == 1) {
                    dp[i][j][1] = -prices[0];
                    continue;
                }
                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][0] - prices[i - 1], dp[i - 1][j][1]);
            }
        }
        return dp[prices.length][k][0];
    }
    
    public int maxProfit2(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        for (int i = 1; i < prices.length + 1; i++) {
            if (i == 1) {
                dp[i][1] = -prices[i - 1];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

这个题如果直接套用模板会出现TLE超时。对于k十分大的corner case需要特殊处理,我们用

k > prices.length / 2

来处理,如果k超过一半了,那么k就相当于无限次使用了。

309. Best Time to Buy and Sell Stock with Cooldown

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        for (int i = 1; i < prices.length + 1; i++) {
            if (i == 1) {
                dp[i][1] = -prices[i - 1];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

dp[i - 1][0]改成dp[i - 2][0],多一天冷却即可。

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

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

买入的时候多减一个fee即可。

参考资料

一个方法团灭 6 道股票问题(翻译了下面的英文版)

Most consistent ways of dealing with the series of stock problems