• Home
  • About
    • Sybil photo

      Sybil

      Sybil's blog.

    • Learn More
    • Email
    • Github
    • Weibo
  • Posts
    • All Posts
    • All Tags
  • Projects

309. 最佳买卖股票时机含冷冻期,动态规划O(N)

17 Mar 2020

预计阅读时间 ~10 分钟

leetcode中等动态规划

解题思路

profit[i][stat]: 表示在第i天,状态为 stat 的时候所能获得的最大收益。

stat 有3种情况

  • 0: 未持有股票,可以买入
  • 1: 已经持有股票,可以卖出
  • 2: 刚卖出股票,正处于冷冻期,无法操作

状态转移方程为:

profit[i][0] = max(profit[i-1][0], // 不操作
                   profit[i-1][2] // 解除冷冻期 
                );
profit[i][1] = max(profit[i-1][1], //继续持有股票
                   profit[i-1][0] - prices[i] // 买入股票
                );
profit[i][2] = max(0, 
                   profit[i-1][1] + prices[i] // 卖出股票
                );

初始化条件为:

profit[0][0] = 0; // 一直未持有
profit[0][1] = - prices[0]; // 买入
profit[0][2] = 0; // 一直未持有
  • 时间复杂度为
  • 空间负责度为

根据 122 题 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/ 的思路写的 dp1.png dp2.png

代码

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        // 在第i天所能获得的最大收益
        // profit[][0]: 表示未持有股票
        // profit[][1]: 表示持有股票
        // profit[][2]: 表示冷冻期
        int[][] profits = new int[prices.length][3];

        // 初始化
        profits[0][0] = 0;
        profits[0][1] = - prices[0];
        profits[0][2] = 0;

        for (int i = 1; i < prices.length; ++i) {
            profits[i][0] = Math.max(profits[i-1][0], // 不操作
                                profits[i-1][2] // 解除冷冻期
                            );
            profits[i][1] = Math.max(profits[i-1][1], // 继续持有股票
                                profits[i-1][0] - prices[i] // 买入股票
                                );
            profits[i][2] = Math.max(0,
                                profits[i-1][1] + prices[i] // 卖出股票
                            );
        }
        return Math.max(profits[prices.length-1][0], profits[prices.length-1][2]);
    }
}


leetcode中等动态规划 Share Tweet +1