您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

小白学习[leetcode]之[动态规划]309. 最佳买卖股票时机含冷冻期

题目的链接在这里:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

目录

  • 题目大意
  • 一、示意图
  • 二、解题思路
    • 动态规划


题目大意

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。


一、示意图

在这里插入图片描述

二、解题思路

 //三种情况分析
            //首先是2表示不持有股票 他可能是两种情况 1.i-1天也不持有 2.i-1是冷却期
            dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
            //然后是0表示持有 可能是i-1天也持有 但是i天没有操作 i-1天没有 但是第i天买入
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i-1]);
            //然后是1表示冷却 只可能是前一天持有股票 并且卖出去了
            dp[i][1]=dp[i-1][0]+prices[i-1];

动态规划

代码如下:

class Solution {
 public int maxProfit(int[] prices) {
        //dp[i][0 1 2]三种情况, 2表示不持有  0表示持有 1表示冷却
        //dp[i][0]表示 第i天手上持有股票,那么第i-1天要么手里有股票,要么就是在冷却期
        //dp[i][1] 表示第i天是冷却期,那么第i-1天手里肯定有股票
        //dp[i][2] 表示没有持股票,并且不在冷却期,那么第i-1天一定没有持有股票
        int len=prices.length;
        //先进行边界判断
        if(prices==null||len==0)
            return 0;
        int dp[][]=new int[len+1][3];
        //首先肯定是 赋初值 dp00说明是持股的 那就是会需要钱
        dp[0][0]=-prices[0];
        //其他情况 冷却期和不持股 都是没钱的
        dp[0][1]=0;;
        dp[0][2]=0;
        //然后开始遍历
        for(int i=1;i<=len;i++){
            //三种情况分析
            //首先是2表示不持有股票 他可能是两种情况 1.i-1天也不持有 2.i-1是冷却期
            dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
            //然后是0表示持有 可能是i-1天也持有 但是i天没有操作 i-1天没有 但是第i天买入
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i-1]);
            //然后是1表示冷却 只可能是前一天持有股票 并且卖出去了
            dp[i][1]=dp[i-1][0]+prices[i-1];
        }
        //最大的利润就是 最后一天不持有股票或者进入冷冻期
        return Math.max(dp[len][2],dp[len][1]);
    }
}

在这里插入图片描述


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进