美文网首页
LeetCode-六道股票问题

LeetCode-六道股票问题

作者: 傅晨明 | 来源:发表于2019-12-06 15:31 被阅读0次

    121. 买卖股票的最佳时机

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

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

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

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

    714. 买卖股票的最佳时机含手续费

    参考：
    https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/39611/Is-it-Best-Solution-with-O(n)-O(1).

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/39608/A-clean-DP-solution-which-generalizes-to-k-transactions

    以188. 买卖股票的最佳时机 IV 为例讲解，因为其他题可以通过这道题演化出来。

    dp[i][k][0 or 1] (0 <= i <= n-1, 1 <= k <= K)

    i 为天数
    k 为最多交易次数 [0,1] 为是否持有股票
    总状态数: n * K * 2 种状态

    for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
             dp[i][k][s] = max(buy, sell, rest)

    状态转移方程：

    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) 
              max(       选择 rest ,        选择 sell )

    解释:今天我没有持有股票，有两种可能:

    • 我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有;
    • 我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(    选择 rest ,     选择 buy )

    解释:今天我持有着股票，有两种可能:

    • 我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票;
    • 我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

    初始状态:

        dp[-1][k][0] = dp[i][0][0] = 0
    dp[-1][k][1] = dp[i][0][1] = -infinity

    状态转移方程:

         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])

    121. 买卖股票的最佳时机

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

    对于k=1，dp[i-1][0][0] = 0(表示没有买过股票并且当前没有持有股票),可以化简去掉所有 k：

        public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -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];
    }

    状态转移方程的新状态只和相邻的一个状态有关，其实不用整个 dp 数组，只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):

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

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

    k 为正无穷，那么就可以认为 k 和 k - 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])
            = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])

我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
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 n = prices.length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -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], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }

    使用变量存储：

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

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

        public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int max_k = 2;
        int[][][] dp = new int[n][max_k + 1][2];

        for (int i = 1; i < n; i++) {
            for (int k = max_k; k >= 1; k--) {
                dp[0][k][0] = 0;
                dp[0][k][1] = -prices[0];

                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][max_k][0];
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int[][][] dp = new int[n][3][2];
        dp[0][2][0] = 0;
        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        dp[0][2][1] = -prices[0];

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

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int dp_i10 = 0;
        int dp_i20 = 0;
//      int dp_i11 = Integer.MIN_VALUE;
//      int dp_i21 = Integer.MIN_VALUE;
        int dp_i11 = -prices[0];
        int dp_i21 = -prices[0];
        for (int price : prices) {
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, -price);
        }
        return dp_i20;
    }

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

        public int maxProfit(int max_k, int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        if (max_k > n / 2)// 超出内存限制
            return maxProfit_k_inf(prices);

        int[][][] dp = new int[n][max_k + 1][2];
        for (int i = 1; i < n; i++)
            for (int k = max_k; k >= 1; k--) {
                dp[0][k][0] = 0;
                dp[0][k][1] = -prices[0];

                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        return dp[n - 1][max_k][0];
    }

    int maxProfit_k_inf(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

    相关文章

      网友评论

          本文标题：LeetCode-六道股票问题

          本文链接：https://www.haomeiwen.com/subject/viesgctx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|LeetCode-六道股票问题|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！