力扣309. 买卖股票的最佳时机含冷冻期(动态规划,Java C++解法)

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

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

Problem: 714. 买卖股票的最佳时机含手续费
该题目可以看作是上述题目的改编,该题目添加了一个冷冻期使得动态转移方程更加复杂,具体思路如下:
1.构建多阶段决策模型:

n天对应n个阶段,每个阶段决策:买股票、卖股票、不操作
买股票:前一天不持有股票,并且处于冷冻期或者处于非冷冻期,而不是刚刚昨天卖掉股票
卖股票:当前持有股票
不操作无规则

2.定义状态:每天都有两种状态:持有股票、不持有股票。不持有股票又分为三小种情况。

int dp[n][4]表示n天的状态
dp[i][0]表示第i天持有股票时的利润
dp[i][1]表示第i天不持有股票时的利润(当天卖掉)
dp[i][2]表示第i天不持有股票时的利润(冷冻期),昨天刚卖掉了股票
dp[i][1]表示第i天不持有股票时的利润(非冷冻期),昨天也没持有

3.定义状态转移方程:

dp[i][0] = max3(dp[i - 1][0], dp[i - 1][2] - prices[i], dp[i - 1][3] - prices[i]);
dp[i][1] = dp[i - 1][0] + prices[i];
dp[i][2] = dp[i - 1][1];
dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3]);

解题方法

1.获取prices数组的长度(假设为n),定义数组int[][] dp = new int[n][4];
2.初始化dp数组的第一行:dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;dp[0][3] = 0;
3.从第一行开始完成动态转移方程;
4.返回dp数组的最后一行的最大值

复杂度

时间复杂度:

O ( n ) O(n) O(n);其中 n n n为数组prices的大小

空间复杂度:

O ( n ) O(n) O(n)

Code

class Solution {
   /**
     * Dynamic programming
     * @param prices Given array(Recode the amount of each stock)
     * @return int
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 1) {
            return 0;
        }
        int[][] dp = new int[n][4];
        /**
         * dp[i][0] represents the profit from holding the stock on day i
         * dp[i][1] represents the profit not held on day i (just sold on the day)
         * dp[i][2] represents the profit from not holding the stock on day i (the freeze period),
         * which was sold yesterday
         * dp[i][3] represents the profit from not holding the stock on day i
         * (non-freezing period) and not holding it yesterday
         */
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        //Dynamic transfer
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i], dp[i - 1][3] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3]);
        }
        return max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]);
    }

    /**
     * Returns the largest number in a set of numbers
     * @param nums Given numbers 
     * @return int
     */
    private int max(int... nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 1) {
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(4));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for (int i = 1; i < n; ++i) {
            dp[i][0] = ::std::max(dp[i - 1][0], ::std::max(dp[i - 1][2] - prices[i], dp[i - 1][3] - prices[i]));
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = ::std::max(dp[i - 1][2], dp[i - 1][3]);
        }
        return ::std::max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]});
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/332007.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【MyBatis-Plus】逻辑删除

对于一些比较重要的数据&#xff0c;我们通常采用逻辑删除。&#xff08;即用一个字段表示是否删除&#xff0c;实际上始终在数据库没有被删除&#xff09; 当逻辑删除字段为 true&#xff0c;业务处理的时候会自动把该数据当做一个“不存在”的数据处理。&#xff08;即不处理…

uniapp让图片缩小

image{width: 500rpx;height:500rpx;} 在图片属性设置为image{}宽高改变但是大小不改变&#xff0c;解决办法是改成下面的代码 & > img {width: 50px; height: auto; } 如图&#xff1a;

最优解:阿里云服务器地域如何选择?

阿里云服务器地域和可用区怎么选择&#xff1f;地域是指云服务器所在物理数据中心的位置&#xff0c;地域选择就近选择&#xff0c;访客距离地域所在城市越近网络延迟越低&#xff0c;速度就越快&#xff1b;可用区是指同一个地域下&#xff0c;网络和电力相互独立的区域&#…

【计算机网络】(1)OSI七层模型、协议、交换技术、路由器技术

文章目录 计算机网络功能与分类计算机网络的定义计算机网络的功能计算机网络的指标计算机网络的性能指标计算机网络的非性能指标 计算机网络的分布范围以及拓扑结构划分图计算机网络分类总线型拓扑星型拓扑环形图拓扑树型拓扑分布式拓扑 通信技术信道物理信道逻辑信道 发信机OS…

vue3-事件处理

事件监听 DOM 事件监听指令 v-on 简写 v-on:click"handler" 或者 click"handler"事件处理器 (handler) 的值可以是&#xff1a; 内联事件处理器&#xff1a;比如 click 方法事件处理器&#xff1a;一个指向组件上定义的方法的属性名或是路径。 在内联…

搭建属于自己的内容付费平台:开发知识付费APP教学

近期知识付费的热度非常高&#xff0c;本篇文章小编将为你提供一份关于如何搭建属于自己的内容付费平台的简要教程&#xff0c;让你能够逐步实现一个功能完备的知识付费APP。 1.明确目标和功能需求 在开始开发之前&#xff0c;首先需要确定你的APP是面向哪个领域的用户&#x…

JSONObject - 用最通俗的讲解,教你玩转 JSON 数据的解析和修改

目录 一、JSONObject 1.1、为什么要使用他&#xff1f; 1.2、应用 1.2.1、依赖 1.2.2、JSON 数据示例 1.2.3、JSON 数据的构建 1.2.4、JSON 数据的解析 一、JSONObject 1.1、为什么要使用他&#xff1f; 在还没有接触过这个东西的时候&#xff0c;一直是通过 ObjectMap…

保护国家机密:Java国密加解密算法在信息安全中的应用与挑战

目录 1、简介 1.1 信息安全的重要性 1.2 Java国密加解密算法的概述 2、Java国密加解密算法的应用 2.1 数据加密与解密 2.2 网络通信加密 2.3 数字签名与验证 2.4 安全存储与传输 3、Java国密加解密算法的特点 3.1 安全性强 3.2 效率高 3.3 弹性可调 4、Java国密加…

(2024,密集量子电路,量子 U-Net,幺正单采样)量子去噪扩散模型

Quantum Denoising Diffusion Models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 2. 相关工作 2.1. 扩散模型 2.2. 变分量子电路 2.3. 量子扩散模型 3. 量子去噪扩散模…

HarmonyOS 转场动画 ForEach控制

本文 我们继续说组件的专场特效 上文 HarmonyOS 转场动画 我们通过if控制了转场效果 本文 我们通过 ForEach 控制它的加载和删除 这时候就有人会好奇 ForEach 怎么控制删除呢&#xff1f; 很简单 循环次数不同 例如 第一次 10个 第二次 5个 那么后面的五个就相当于删除啦 我们…

JVM垃圾回收机制及思维导图

一、Java垃圾回收机制 在java中&#xff0c;程序员是不需要显示的去释放一个对象的内存的&#xff0c;而是由虚拟机自行执行。在JVM中&#xff0c;有一个垃圾回收线程&#xff0c;它是低优先级的&#xff0c;在正常情况下是不会执行的&#xff0c;只有在虚拟机空闲或者当前堆内…

【Alibaba工具型技术系列】「EasyExcel技术专题」实战技术针对于项目中常用的Excel操作指南

这里写目录标题 EasyExcel教程Maven依赖 EasyExcel API分析介绍EasyExcel 注解通用参数ReadWorkbook&#xff08;理解成excel对象&#xff09;参数ReadSheet&#xff08;就是excel的一个Sheet&#xff09;参数注解参数通用参数 WriteWorkbook&#xff08;理解成excel对象&#…

k8s学习-Deployment

Kubernetes通过各种Controller来管理Pod的生命周期 。 为了满足不同业 务 景 &#xff0c; Kubernetes 开发了Deployment、ReplicaSet、DaemonSet、StatefuleSet、Job等多种Controller。我们⾸先学习最常用Deployment。 1.1 Kubectl命令直接创建 第一种是通过kubectl命令直接…

java读取配置文件数据

在实际开发中&#xff0c;项目中难免会有一些秘钥或者不经常使用到的配置信息&#xff0c;此时&#xff0c;就可以将这些配置信息统一写到配置文件中。随后使用Value注解读取配置文件的值来向Spring中Bean的属性设置值。 例如&#xff0c;一些系统环境变量信息&#xff0c;数据…

路飞项目--02

补充&#xff1a;axios封装 # 普通使用&#xff1a;安装 &#xff0c;导入使用 const filmListreactive({result:[]}) axios.get().then() async function load(){let responseawait axios.get()filmList.resultresponse.data.results } # 封装示例&#xff1a;请求发出去之前…

让代码运行得更快:深入理解进程、线程和协程

让代码运行得更快&#xff1a;深入理解进程、线程和协程 什么是执行体 在深入探讨进程、线程和协程之前&#xff0c;我想先介绍下执行体这个概念。 执行体这个词语是我从七牛云创始人许式伟大佬的专栏中学到的&#xff0c;它代表操作系统中程序执行的载体&#xff0c;涉及到…

makefile,make,gcc/g++ 编译流程分析

文章目录 makefile&#xff0c;make&#xff0c;gcc/g 编译流程分析 makefile&#xff0c;make&#xff0c;gcc/g 编译流程分析 C实现加减乘除四个运算 // // Created by qiufh on 2024-01-17. //#include "add.h"int add(int a, int b) {return a b; } // // Cre…

C++的命名空间域

一、域作用限定符 :: 即是域作用限定符&#xff0c;它的作用是指明一个标识符&#xff08;变量、函数或类&#xff09;来自哪一个作用域范围 二、编译器搜索变量、函数等的原则 1.先搜索局部变量&#xff0c;2.再搜索全局变量&#xff0c;3.最后搜索指定的命名空间域 三、…

python数字图像处理基础(十)——背景建模

目录 背景建模背景消除-帧差法混合高斯模型 背景建模 背景建模是计算机视觉和图像处理中的一项关键技术&#xff0c;用于提取视频中的前景对象。在视频监控、运动检测和行为分析等领域中&#xff0c;背景建模被广泛应用。其基本思想是通过对视频序列中的像素进行建模&#xff…

构建中国人自己的私人GPT—限时免费部署

在现实生活中&#xff0c;很多公司或个人的资料是不愿意公布在互联网上的&#xff0c;但是我们又要使用人工智能的能力帮我们处理文件、做决策、执行命令那怎么办呢&#xff1f;于是我们构建自己或公司的本地专属GPT变得非常重要。 先看效果&#xff1a; 解方程&#xff0c;24小…