Day50|动态规划part11:188.买卖股票的最佳时机IV、123. 买卖股票的最佳时机III

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

leetcode链接:188 题「买卖股票的最佳时机 IVopen in new window」

视频链接:动态规划来决定最佳时机,至多可以买卖K次!| LeetCode:188.买卖股票最佳时机4

给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,
你最多可以买 k 次,卖 k 次。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1(股票价格 = 2) 的时候买入,在第 2(股票价格 = 4) 的时候卖出,
  这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2(股票价格 = 2) 的时候买入,在第 3(股票价格 = 6) 的时候卖出, 
  这笔交易所能获得利润 = 6-2 = 4 。
  随后,在第 5(股票价格 = 0) 的时候买入,在第 6(股票价格 = 3) 的时候卖出,
  这笔交易所能获得利润 = 3-0 = 3

接下来的解法来自labuladong的算法 ,从最难的188题入手,限制最多。用状态机的形式进行状态转移。

对于每天的股票,有三种选择:买,卖,不买也不卖。我们用 buy, sell, rest 表示这三种选择。但每次这三种状态不是随便选的:

  • 因为 sell 必须在 buy 之后(对于交易次数设置为无限次时,只能先卖掉手里的再买)
  • buy 必须在 sell 之后(手里有股票了才能卖)。
  • 那么 rest 操作还应该分两种状态,一种是 buy 之后的 rest(持有了股票),一种是 sell 之后的 rest(没有持有股票)。
  • 交易次数 k 的限制,就是说你 buy 还只能在 k > 0 的前提下操作
  1. 确定dp数组的含义及下标

我们的dp数组应该是几维的?这个问题的「状态」有三个,第一个是天数,第二个是允许交易的最大次数,第三个是当前的持有状态(即之前说的 rest 的状态,我们不妨用 1 表示持有,0 表示没有持有)。然后我们用一个三维数组就可以装下这几种状态的全部组合:

dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数,大 K 为交易数的上限,01 代表是否持有股票。
此问题共 n × K × 2 种状态,全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

比如说 dp[3][2][1] 的含义就是:今天是第三天,我现在手上持有着股票,至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义:今天是第二天,我现在手上没有持有股票,至今最多进行 3 次交易。

我们想求的最终答案就是:dp[n - 1][k][0] ,因为最后一天卖出肯定比不卖出赚的多,因此求的不是dp[n-1][k][1]

  1. 确定递推公式

我们可以画出如下的状态转移图:

image

因此我们可以分两种状态:dp[i][k][0]和dp[i][k][1]

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max( 今天选择 rest,        今天选择 sell       )

解释:今天我没有持有股票,有两种可能,我从这两种可能中求最大利润:

1、我昨天就没有持有,且截至昨天最大交易次数限制为 k;然后我今天选择 rest,所以我今天还是没有持有,最大交易次数限制依然为 k

2、我昨天持有股票,且截至昨天最大交易次数限制为 k;但是今天我 sell 了,所以我今天没有持有股票了,最大交易次数限制依然为 k

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max( 今天选择 rest,         今天选择 buy         )

解释:今天我持有着股票,最大交易次数限制为 k,那么对于昨天来说,有两种可能,我从这两种可能中求最大利润:

1、我昨天就持有着股票,且截至昨天最大交易次数限制为 k;然后今天选择 rest,所以我今天还持有着股票,最大交易次数限制依然为 k

2、我昨天本没有持有,且截至昨天最大交易次数限制为 k - 1;但今天我选择 buy,所以今天我就持有股票了,最大交易次数限制为 k

  • 状态 k 的定义并不是「已进行的交易次数」,而是「最大交易次数的上限限制」。
  • sell 的时候给 k 减小 1 和在 buy 的时候给 k 减小 1 是并不是等效,因为交易是从 buy 开始,如果 buy 的选择不改变交易次数 k 的话,会出现交易次数超出限制的的错误。也就是说买的时候k - 1卖的时候不减。

这是一个反向的过程,是推图的入边而不是出边。

  1. 确定dp初始化
dp[-1][...][0] = 0
解释:因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润当然是 0。

dp[-1][...][1] = -infinity
解释:还没开始的时候,是不可能持有股票的。
因为我们的算法要求一个最大值,所以初始值设为一个最小值,方便取最大值。

dp[...][0][0] = 0
解释:因为 k 是从 1 开始的,所以 k = 0 意味着根本不允许交易,这时候利润当然是 0。

dp[...][0][1] = -infinity
解释:不允许交易的情况下,是不可能持有股票的。
因为我们的算法要求一个最大值,所以初始值设为一个最小值,方便取最大值。

至于-1 怎么编程表示出来呢,负无穷怎么表示呢?这都是细节问题,有很多方法实现。

  1. 确定遍历顺序

因此天数是从小到大的,因此遍历顺序肯定是从前往后。

  1. 循环打印dp数组

这样我们就确定了买卖股票问题的框架,其他的题目都是这题的特殊情况。

最终代码(这里从123题的题解简化而来)

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int max_k = k;
        vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(max_k + 1, vector<int>(2,0)));
        for(int i = 0; i < prices.size(); i++){
            for(int k1 = max_k; k1 >= 1; k1--) {
                if (i - 1 == -1) {
                    dp[i][k1][0] = 0;
                    dp[i][k1][1] = -prices[i];
                    continue;
                }
                dp[i][k1][0] = max(dp[i - 1][k1][0], dp[i - 1][k1][1] + prices[i]);
                dp[i][k1][1] = max(dp[i - 1][k1][1], dp[i - 1][k1 - 1][0] - prices[i]);
            }
        }
        return dp[prices.size() - 1][max_k][0];
    }
};

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

leetcode链接:力扣题目链接

视频链接:动态规划,股票至多买卖两次,怎么求? | LeetCode:123.买卖股票最佳时机III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,
  这笔交易所能获得利润 = 3-0 = 3 。
  随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,
  这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出,
  这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:

输入:prices = [7,6,4,3,1] 
输出:0 
解释:在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4:

输入:prices = [1]
输出:0

实际上,这题就是一般情况下k = 2的情况。

  1. dp数组含义及其下标

dp[i][k][0]/dp[i][k][1]表示第i天在最大贸易次数为k的情况下持有股票/不持有股票的最大利润。

  1. 确定递推公式
原始的状态转移方程,没有可化简的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
  1. 确定dp数组的初始化

这里的max_k是自己设定的,最多交易两次,max_k = 2。注意这里的初始化是在for循环中进行的,在i = 0的时候初始化,因为k需要穷举。

for(int k = max_k; k >= 1; k--) {
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
  1. 确定遍历顺序

我们这里k是逆序的,比较符合常理:

你买股票,初始的「状态」是什么?应该是从第 0 天开始,而且还没有进行过买卖,所以最大交易次数限制 k 应该是 max_k;而随着「状态」的推移,你会进行交易,那么交易次数上限 k 应该不断减少,这样一想,k = max_k, k-- 的方式是比较合乎实际场景的。

  1. 打印dp数组

最终代码:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_k = 2;
        vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(max_k + 1, vector<int>(2,0)));
        for(int i = 0; i < prices.size(); i++){
            for(int k = max_k; k >= 1; k--) {
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[prices.size() - 1][max_k][0];
    }
};

空间复杂度简化版本(还是很难看懂):

// 空间复杂度优化版本
class Solution {
public:
    int maxProfit_k_2(vector<int>& prices) {
      // 状态转移方程:
// dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
// dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
// dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
// dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
        // base case
        int dp_i10 = 0, dp_i11 = INT_MIN;
        int dp_i20 = 0, dp_i21 = INT_MIN;
        for (int price : prices) {
            dp_i20 = max(dp_i20, dp_i21 + price);
            dp_i21 = max(dp_i21, dp_i10 - price);
            dp_i10 = max(dp_i10, dp_i11 + price);
            dp_i11 = max(dp_i11, -price);
        }
        return dp_i20;
    }
};

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

leetcode链接:力扣题目链接

视频链接:动态规划来决定最佳时机,这次有冷冻期!| LeetCode:309.买卖股票的最佳时机含冷冻期

给定一个整数数组 prices,其中第 prices[i] 表示第 i 天的股票价格 。​

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

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

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:

输入: prices = [1]
输出: 0

这题相比买卖股票II 添加了冷冻的限制,但其实k还是无穷的,把II的代码修改一下即可:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp (prices.size(),vector<int>(2));
        int cooldown = 1;//本题的冷却期为1天
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1; i < prices.size(); i++){
            if(i - cooldown - 1 < 0){//防止数组越界,或者说在这段时间内i很短,不需要冷静期
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = max(dp[i-1][1], -prices[i]);
                continue;
            }
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i- cooldown - 1][0] -prices[i]);

        }
        return dp[prices.size() - 1][0];
    }
};

注意这里的dp[i][1]有变化,分析一下:dp[i][1]表示到状态1的两种情况,第一个是rest,从前一天开始就持有股票且不仍然不卖出,此时就是dp[i - 1][1],第二种情况是从前i - cooldown-1天买入,因为有冷冻期,故经过cooldown天才能在第二天买入。

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

leetcode链接:力扣题目链接

视频链接:动态规划来决定最佳时机,这次含手续费!| LeetCode:714.买卖股票的最佳时机含手续费

给定一个整数数组 prices,其中第 prices[i] 表示第 i 天的股票价格 。​

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

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

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:

输入: prices = [1]
输出: 0

这题加入了手续费的限制,k还是无限大,还是买卖股票II的变体。最终代码:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp (prices.size(),vector<int>(2));
        dp[0][0] = 0;
        dp[0][1] = -( prices[0]);
        for(int i = 1; i < prices.size(); i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] -prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};

注意这里手续费在一次交易(一次买入,一次卖出)中只需要交一次,故在卖出的时候交手续费就可以了,比较方便。

总结

  • 买卖股票加入k之后,因为要穷举所有的状态,因此还要加一层循环对k进行穷举。
  • 注意三维数组的vector写法:
vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>
(max_k + 1, vector<int>(2,0)));
  • 无论是加入手续费还是冷静期,原理基本还是一样的。略微修改递归公式即可。若与天数相关就改变下标i,若与费用相关就改变price

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

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

相关文章

递归算法学习——子集

目录 一&#xff0c;题目解析 二&#xff0c;例子 三&#xff0c;题目接口 四&#xff0c;解题思路以及代码 1.完全深度搜索 2.广度搜索加上深度优先搜索 五&#xff0c;相似题 1.题目 2.题目接口 3.解题代码 一&#xff0c;题目解析 给你一个整数数组 nums &#xff0c…

Acwing796.子矩阵的和

理解二维前缀和&#xff1a; #include <iostream>using namespace std;const int N 1010;int a[N][N], s[N][N];int main() {int n, m, q;cin >> n >> m >> q;for (int i 1; i < n; i)for (int j 1; j < m; j) {scanf("%d", &a…

2023高教社杯数学建模思路 - 复盘:光照强度计算的优化模型

文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米&#xff0c;宽为12米&…

本地部署 CodeLlama 并在 VSCode 中使用 CodeLlama

本地部署 CodeLlama 并在 VSCode 中使用 CodeLlama 1. CodeLlama 是什么2. CodeLlama Github 地址3. 下载 CodeLlama 模型4. 部署 CodeLlama5. 在 VSCode 中使用 CodeLlama6. 使用WSGI启动服务7. 创建 start.sh 启动脚本 1. CodeLlama 是什么 Code Llama 是一个基于 Llama 2 的…

WebSocket详解以及应用

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;websocket、网络、长连接、前端☀️每日 一言&#xff1a;任何一个你不喜欢而又离不开的地方&#xff0c;任何一种你不喜欢而又无法摆脱的生活&#xff0c;都是监狱&#xff01; 一、前言 我们在…

用wireshark流量分析的四个案例

目录 第一题 1 2 3 4 第二题 1 2 3. 第三题 1 2 第四题 1 2 3 第一题 题目&#xff1a; 1.黑客攻击的第一个受害主机的网卡IP地址 2.黑客对URL的哪一个参数实施了SQL注入 3.第一个受害主机网站数据库的表前缀&#xff08;加上下划线例如abc&#xff09; 4.…

智慧展馆展厅5G+LoRa+蓝牙人员定位系统解决方案

展览业是现代高端服务业的重要组成部分&#xff0c;作为新兴的服务行业&#xff0c;展览业串联着工业、农业、商贸等诸多产业&#xff0c;能够有效拉动产业和消费增长&#xff0c;是中国发展潜力较大的行业之一。如今各个行业越来越多地举办各类展会&#xff0c;由于展馆展厅规…

按照json文件的值复制图片

按照json文件的值复制图片 文件格式处理当前JSON代码封装增加批处理 文件格式 0是不挑选&#xff0c;1是挑选 处理当前JSON # coding: utf-8 from PIL import Image, ImageDraw, ImageFont import os import shutil import cv2 as cv import numpy as np import jsondef read…

Rabbitmq的消息转换器

Spring会把你发送的消息序列化为字节发送给MQ&#xff0c;接收消息的时候&#xff0c;还会把字节反序列化为Java对象 ,只不过&#xff0c;默认情况下Spring采用的序列化方式是JDK序列化。众所周知&#xff0c;JDK序列化存在下列问题&#xff1a; 数据体积过大 有安全漏洞 可读…

java 桥接模式

桥接模式 桥接模式简介桥接模式的实现总结 桥接模式简介 桥接模式&#xff08;Bridge&#xff09;是将抽象部分与它的实现部分分离&#xff0c;使它们都可以独立地变化。它是一种对象结构型模式&#xff0c;又称为柄体(Handle and Body)模式或接口(Interfce)模式。 桥接模式基于…

二级MySQL(十)——单表查询

这里我们只在一个表内查询&#xff0c;用到的是较为简单的SELECT函数形式 1、查询指定的字段&#xff1a; 用到的数据库是之前提到的S、P、SP数据库 S表格用到的总数据&#xff1a; 首先我们查询所有供应商的序号和名字 这时都是独立的&#xff0c;没有关系&#xff0c;我们找…

用P,V操作解决进程同步问题的解题步骤(优化版)

蓝颜色是格外注意的 还有读读共享&#xff0c;读写互斥问题。 要背会四个模式&#xff0c;套用模式 例题讲解1&#xff09;生产者-消费者问题 一般意义的“生产者—消费者”问题&#xff1a;N个buffer&#xff0c;多个生产者&#xff0c;多个消费者&#xff0c;循环存取buffer。…

js删除字符串中的指定字符串

1. 使用 replace() 方法 replace() 将字符串中的指定子字符串替换为新的字符串。 如果删除指定的子字符串&#xff0c;可以将它替换为空字符串。 var str "Hello, World!";var substringToRemove "World";var newStr str.replace(substringToRemove, &q…

Ansible学习笔记8

group模块&#xff1a; 创建一个group组&#xff1a; [rootlocalhost ~]# ansible group1 -m group -a "nameaaa gid5000" 192.168.17.105 | CHANGED > {"ansible_facts": {"discovered_interpreter_python": "/usr/bin/python"}…

亚马逊云科技 云技能孵化营——我的云技能之旅

文章目录 每日一句正能量前言活动流程后记 每日一句正能量 不能在已经获得足够多的成功时&#xff0c;还对自己的能力保持怀疑&#xff0c;露出自信的微笑&#xff0c;走出自信的步伐&#xff0c;做一个自信的人&#xff01; 前言 亚马逊云科技 (Amazon Web Services) 是全球云…

【论文笔记】最近看的时空数据挖掘综述整理8.27

Deep Learning for Spatio-Temporal Data Mining: A Survey 被引用次数&#xff1a;392 [Submitted on 11 Jun 2019 (v1), last revised 24 Jun 2019 (this version, v2)] 主要内容&#xff1a; 该论文是一篇关于深度学习在时空数据挖掘中的应用的综述。论文首先介绍了时空数…

从传统软件开发到云原生转型:大数据和AI如何引领软件开发的新趋势

文章目录 **1. 数据驱动的开发&#xff1a;****2. 智能化的用户体验&#xff1a;****3. 云原生的可扩展性&#xff1a;****4. 实时处理和决策&#xff1a;****5. 自动化和效率提升&#xff1a;****6. 持续集成和交付的加速&#xff1a;****7. 数据安全和隐私&#xff1a;****8.…

1427205-93-3|Fmoc-Ser(Ac4Manα1-2Ac3Manα1-2Ac3Manα)-OH是指糖类与氨基酸通过糖苷键连接而成的化合物

糖基化氨基酸是指糖类与氨基酸通过糖苷键连接而成的化合物。这种糖苷键的形成是由于糖类的末端羟基与氨基酸的氨基之间发生脱水缩合反应糖。基化氨基酸具有多种生物学功能&#xff0c;如作为酶、激素和抗体的成分&#xff0c;参与细胞识别和信息传递等。 在生物体内&#xff0c…

【C++小项目】实现一个日期计算器

目录 Ⅰ. 引入 Ⅱ. 列轮廓 Ⅲ. 功能的实现 构造函数 Print 判断是否相等 | ! ➡️: ➡️!: 判断大小 > | > | < | < ➡️>&#xff1a; ➡️<&#xff1a; ➡️>&#xff1a; ➡️<&#xff1a; 加减天数 | | - | - ➡️&#xff1a;…

Java CompletableFuture 详细使用教程与实践

一、Java CompletableFuture 详细使用教程 Java 8引入了一种强大的异步编程工具&#xff1a;CompletableFuture。它提供了一种处理异步计算的方式&#xff0c;使得你可以在计算完成时获取结果&#xff0c;或者将一个或多个 CompletableFuture 的结果组合在一起。本部分将详细解…