代码随想录算法训练营第五十天 | LeetCode 309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费、股票系列总结

简介: 代码随想录算法训练营第五十天 | LeetCode 309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费、股票系列总结

代码随想录算法训练营第五十天 | LeetCode 309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费、股票系列总结

文章链接:买卖股票的最佳时机含冷冻期买卖股票的最佳时机含手续费股票系列总结

视频链接:买卖股票的最佳时机含冷冻期买卖股票的最佳时机含手续费

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

1.1 思路

  1. 本题是在122. 买卖股票的最佳时机 II的基础上加了个冷冻期,是可以多次买卖股票的,本题是在卖出股票后会有 1 天冷冻期即不能买了
  2. dp 数组及其下标的含义:dp[i][0] 是持有的状态,可以是当前买入或者前几天买入一直保持持有;dp[i][1] 保持卖出的状态(即冷冻期之后到买入的之前的状态,可以买入但不买的状态);dp[i][2] 具体卖出的状态(即冷冻期前卖出股票的状态);对于这里其实是把不持有的状态分成了 dp[i][1] 和 dp[i][2];dp[i][3] 即冷冻期,持续一天
  3. 递推公式:dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]))即延续前一天持有股票的状态,或者前一天是冷冻期恢复后买入,又或者前一天是保持卖出的状态然后买入;dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3])即延续前一天保持卖出的状态,或者前一天是冷冻期;dp[i][2]=dp[i-1][0]+prices[i]即前一天是持有股票的然后卖出了;dp[i][3]=dp[i-1][2],即前一天是刚卖出的状态
  4. dp 数组的初始化:dp[0][0]=-prices[i];dp[0][1] 这个状态本来就是不合理的状态,看看递推公式需要把它初始化成什么,在第 1 天变为持有的状态 dp[1][0]=Math.max(dp[0][0],Math.max(dp[0][3]-prices[0],dp[0][1]-prices[0]))可以看出应该把 dp[0][1] 初始化为 0;dp[0][2] 也是初始化为 0,同理是个不合理的状态,或者理解为当天买当天卖;dp[0][3]=0,同样是不合理的状态
  5. 遍历顺序:根据递推公式就是从前往后遍历。最终返回 Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]))即将后面的三个状态取最大值
  6. 打印 dp 数组:用于 debug

1.2 代码

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

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

2.1 思路

  1. 本题是在122. 买卖股票的最佳时机 II的基础上在卖出的时候多加了手续费
  2. dp 数组及其下标的含义:dp[i][1] 是不持有股票的最大现金,dp[i][0] 是持有股票的最大现金
  3. 递推公式: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]-fee)即保持前一天不持有的状态,或者前一天持有然后卖出的状态再减去手续费
  4. dp 数组的初始化:dp[0][0]=-prices[0],dp[0][1]=0
  5. 遍历顺序:从前往后
  6. 打印 dp 数组:用于 debug

2.2 代码

/**
 * 卖出时支付手续费
 * @param prices
 * @param fee
 * @return
 */
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    // 0 : 持股(买入)
    // 1 : 不持股(售出)
    // dp 定义第i天持股/不持股 所得最多现金
    int[][] dp = new int[len][2];
    dp[0][0] = -prices[0];
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
}

3. 股票系列总结

3.1 121. 买卖股票的最佳时机

在数组中只能买卖一次,定义了两个状态,dp[i][0] 持有,dp[i][1] 不持有

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices[i] 所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

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

在数组中可以买卖多次了,和121. 买卖股票的最佳时机一样,也是定义两个状态,dp[i][0] 持有,dp[i][1] 不持有

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]

注意:在121. 买卖股票的最佳时机中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即dp[i][0]一定就是 -prices[i]。而本题,因为一只股票可以买卖多次,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润。

如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

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

在数组中至多买卖两次,定义了五个状态,第 i 天 dp[i][0] 表示不操作,dp[i][1] 表示第 1 次持有,dp[i][2] 表示第 1 次不持有,dp[1][3] 表示第 2 次持有,dp[i][4] 表示第 2 次不持有

dp[i][j]中 i表示第i天,j为 [0 - 4] 五个状态,dp[i][j]表示第i天状态j所剩最大现金。

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]
  • 即dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
  • 所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分:

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

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

在数组中至多买卖 k 次,和123. 买卖股票的最佳时机 III其实一样的,只是做了个抽象化,dp 数组的二维的下标通过一个变量来表示,方便至多买卖 k 次,表示对应的状态

使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j]

j的状态表示为:

  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出

  • 除了0以外,偶数就是卖出,奇数就是买入

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i - 1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]
  • dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
  • dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可以类比剩下的状态

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

含有冷冻期,这里其实也算是两个状态 dp[i][0] 持有,dp[i][1] 不持有,但把不持有分成 3 个状态了,变为 dp[i][1] 保持卖出的状态,dp[i][2] 具体卖出的状态,dp[i][3] 冷冻期

dp[i][j]:第i天状态为j,所剩的最多现金为dp[i][j]。

  • 状态一:买入股票状态(今天买入股票,或者是之前就买入了股票然后没有操作)
  • 卖出股票状态,这里就有两种卖出股票状态
  • 状态二:两天前就卖出了股票,度过了冷冻期,一直没操作,今天保持卖出股票状态
  • 状态三:今天卖出了股票
  • 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!

达到买入股票状态(状态一)即:dp[i][0],有两个具体操作:

  • 操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]
  • 操作二:今天买入了,有两种情况
  • 前一天是冷冻期(状态四),dp[i - 1][3] - prices[i]
  • 前一天是保持卖出股票状态(状态二),dp[i - 1][1] - prices[i]
    所以操作二取最大值,即:max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
    那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);

达到保持卖出股票状态(状态二)即:dp[i][1],有两个具体操作:

  • 操作一:前一天就是状态二
  • 操作二:前一天是冷冻期(状态四)
    dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态(状态三),即:dp[i][2] ,只有一个操作:

  • 操作一:昨天一定是买入股票状态(状态一),今天卖出
    即:dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态(状态四),即:dp[i][3],只有一个操作:

  • 操作一:昨天卖出了股票(状态三)
    dp[i][3] = dp[i - 1][2];

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

就是在122. 买卖股票的最佳时机 II的基础上卖出的时候多了手续费

dp数组的含义:

dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]
    所以:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金,注意这里需要有手续费了即:dp[i - 1][0] + prices[i] - fee
    所以:dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
相关文章
|
2天前
|
人工智能 算法 数据可视化
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
21 0
|
2天前
|
机器学习/深度学习 存储 监控
yolov5单目测距+速度测量+目标跟踪(算法介绍和代码)
yolov5单目测距+速度测量+目标跟踪(算法介绍和代码)
28 1
|
3天前
|
机器学习/深度学习 算法 测试技术
低照度增强算法(图像增强+目标检测+代码)
低照度增强算法(图像增强+目标检测+代码)
19 1
|
3天前
|
机器学习/深度学习 监控 算法
yolov8+多算法多目标追踪+实例分割+目标检测+姿态估计(代码+教程)
yolov8+多算法多目标追踪+实例分割+目标检测+姿态估计(代码+教程)
22 1
|
2天前
|
存储 人工智能 算法
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
18 0
|
1天前
|
算法
动态规划之第 N 个泰波那契数/三步问题【leetCode】【算法】
动态规划之第 N 个泰波那契数/三步问题【leetCode】【算法】
|
12天前
|
算法
MATLAB | 插值算法 | 一维interpl插值法 | 附数据和出图代码 | 直接上手
MATLAB | 插值算法 | 一维interpl插值法 | 附数据和出图代码 | 直接上手
20 0
|
12天前
|
算法
MATLAB | 插值算法 | 二维interp2插值法 | 附数据和出图代码 | 直接上手
MATLAB | 插值算法 | 二维interp2插值法 | 附数据和出图代码 | 直接上手
15 0
|
2月前
|
算法 Java
[Java·算法·简单] LeetCode 9. 回文数 详细解读
[Java·算法·简单] LeetCode 9. 回文数 详细解读
22 0
|
2月前
|
算法
LeetCode算法题---最长回文子串、N 字形变换(四)
LeetCode算法题---最长回文子串、N 字形变换(四)
20 0

相关产品