代码随想录算法训练营第四十四天|188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

admin2024-07-05  42

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

代码随想录算法训练营第四十四天|188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费,在这里插入图片描述,第1张

思路:
在股票买卖1使用一维dp的基础上,升级成二维的即可。

  1. 定义dp[k+1][2],其中 dp[j][0] 表示第j次交易后持有股票的最大利润,dp[j][1] 表示第j次交易后不持有股票的最大利润。
  2. 初始化时,对所有持有股票的情况要变成dp[i][0] = -prices[0];

题解:
要注意: dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票

    public int maxProfit(int k, int[] prices) {
        // 特殊情况处理,如果价格数组为空或只有一个元素,返回0
        if (prices.length == 0) return 0;

        // dp数组定义为k+1行,2列
        // dp[j][0] 表示第j次交易后持有股票的最大利润
        // dp[j][1] 表示第j次交易后不持有股票的最大利润
        int[][] dp = new int[k + 1][2];

        // 初始化第1到第k次交易后的持有股票的最大利润为 -prices[0]
        for (int i = 1; i <= k; i++) {
            dp[i][0] = -prices[0];
        }

        // 遍历每一天的股票价格
        for (int i = 1; i < prices.length; i++) {
            // 倒序遍历每一次交易,也可以正序,但是倒序更快一点
            for (int j = k; j >= 1; j--) {
                // 更新第j次交易后不持有股票的最大利润
                dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);
                // 更新第j次交易后持有股票的最大利润
                // dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票
                dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
            }
        }

        // 返回最多k次交易后不持有股票的最大利润
        return dp[k][1];
    }

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

代码随想录算法训练营第四十四天|188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费,在这里插入图片描述,第2张

思路:

第i天的最大收益由持有和不持有股票两种状态推导出来,考虑到由冷冻期,那么第i天持有股票可以考虑跳过昨天,从前天推导。

假设有今天持股情况下的最大收益 dp[i][0]、昨天不持股的最大收益 dp[i−1][0]、昨天持股的最大收益 dp[i−1][0]、前天不持股的最大收益 dp[i−2][1],前天持股的最大收益 dp[i−2][0]。先将目光集中在前天,分别考虑前天持股与不持股的情况,试试能不能推导出今天的最大收益。

对于 dp[i−2][0] 来说,它表示前天结束时手中还有股票,那么如果昨天选择将前天的股票卖掉,由于冷冻期的存在,今天是不能交易的,自然今天手中也不可能还有股票,推导不出 dp[i][0],因此这种情况可以直接忽略;如果前天选择保留股票到昨天,昨天也只能继续保留股票才能让今天手中也有股票,这时 dp[i][0]=dp[i−1][0],这种情况已经在上面的状态转移方程中考虑到了,因此也不用担心。
对于 dp[i−2][1] 来说,它表示前天结束时手中没有股票,如果昨天买入股票,只能是将股票保留到今天才能推出 dp[i][0],这时 dp[i]=dp[i−1][0] 在状态转移方程中已经考虑到了;如果昨天不买入股票,那么由于昨天手中没有股票,只能是今天买入,同时因为昨天没交易,昨天的最大收益和前天相同 dp[i−1][1]=dp[i−2][1],所以这种情况的最大收益是 dp[i−2][1]−prices[i]。

题解:

   public int maxProfit(int[] prices) {
        int n = prices.length;

        // 如果价格数组长度为0,直接返回0
        if (n == 0) {
            return 0;
        }

        // 定义一个二维数组 dp,dp[i][0] 表示第 i 天持有股票的最大利润,
        // dp[i][1] 表示第 i 天不持有股票的最大利润
        int[][] dp = new int[n + 1][2];

        // 初始化第一天的状态
        dp[1][0] = -prices[0]; // 第一天持有股票,利润为负的当前股票价格

        // 从第二天开始遍历价格数组
        for (int i = 2; i <= n; i++) {
            // 第 i 天持有股票的最大利润,可以选择前一天也持有股票,或者前两天不持有股票,今天买入
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);

            // 第 i 天不持有股票的最大利润,可以选择前一天也不持有股票,或者前一天持有股票,今天卖出
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);
        }

        // 返回倒数第二天不持有股票的最大利润
        return dp[n][1]; // 因为是倒数第二天,所以这里改为 dp[n][1]
    }

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

代码随想录算法训练营第四十四天|188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费,在这里插入图片描述,第3张

思路:和股票买卖第2道题一样,不过每次卖出的时候扣除手续费就好了。

题解:

public int maxProfit(int[] prices, int fee) {
    if (prices.length == 1) {
        return 0;
    }
    int hasStock = -prices[0]; // 第一天买入股票后的收益
    int noStock = 0; // 第一天不买股票的收益
    for (int i = 1; i < prices.length; i++) {
        // 今天选择买入股票或者保持昨天持有股票的状态
        hasStock = Math.max(hasStock, noStock - prices[i]);
        // 今天选择卖出股票或者保持昨天没有股票的状态
        noStock = Math.max(noStock, hasStock + prices[i] - fee);
    }
    return noStock; // 最后一天不持有股票的最大收益
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!