【LeetCode动态规划#13】买卖股票含冷冻期(状态众多,比较繁琐)、含手续费

这篇具有很好参考价值的文章主要介绍了【LeetCode动态规划#13】买卖股票含冷冻期(状态众多,比较繁琐)、含手续费。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

力扣题目链接(opens new window)

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

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

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

示例:

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

思路

本题在买卖II的基础上多了一个条件:即卖出股票后的一天不能交易(冷冻期)

我们在分析买卖II时有:持有不持有 两种状态,并且这两种状态中又细分为 当天买入/卖出 和 前一天买入/卖出

因为本题加了冷冻期,所以状态会有不同,大体上可以分为:持有股票不持有股票处于冷冻期三大类

五步走

1、确定dp数组含义

持有股票可以视为状态1(今天买入或者前一天买入,因为引入了冷冻期,其中还有细分情况后面说)

基于此,我觉得买卖II的状态也是可以缩减的(但这么做可能就不够直观了)

因为有冷冻期限制卖出的操作,所以不持有股票时还是要细分为两种情况

保持之前不持有股票的状态视为状态2

今天卖出股票视为状态3

最后,也是新增的一个状态,即卖出股票后的冷冻期,视为状态4

综上,本题一共有以下四种状态:

状态1---持有股票(j = 0)

不持有股票
	状态2---保持不持有状态(j = 1)
	状态3---今天卖掉股票(j = 2)
状态4---冷冻期(j = 3)

和买卖II一样,我们仍需要使用二维dp数组dp[i][j]来表示状态:代表第i天某种状态下得到的最大收益

2、确定递推公式
(1)持有(买入)股票dp[i][0](状态1)

要达到dp[i][0],可以有两个途径:今天买入股票前一天买入股票

  • 今天买入股票又分为三种情况

    • (买入)前一天是冷冻期(状态4,j = 3),即冷冻期一结束马上买入,dp[i][0] = dp[i - 1][3] - prices[i]
    • (买入)前一天是不持有股票状态(状态2,j = 1),即昨天之前就已经卖掉股票并过了冷冻期,但是还没有买入股票,今天买入dp[i][0] = dp[i - 1][1] - prices[i]

    两者取最大值max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

    • (维持状态即前一天买入股票)前一天是保持着上一天买入的状态(状态1,j = 0),并持续到今天,dp[i][0] = dp[i - 1][0]

综上,持有股票状态(状态1)的递推公式是:dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));

(2)不持有股票,保持不持有状态dp[i][1](状态2)
  • 前一天为冷冻期(状态4,j = 3),即两天之前卖掉了股票,经过一天冷冻期到今天就是不持有状态(不用再加prices),dp[i][1] = dp[i - 1][3]
  • 前一天就是不持有股票的状态(状态2,j = 1),即在昨天之前就已经卖掉股票并度过了冷冻期dp[i][1] = dp[i - 1][1]

综上,保持不持有状态(状态2)的递推公式是:dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

(3)今天卖掉股票dp[i][2](状态3)
  • 前一天为冷冻期(状态4,j = 3),即冷冻期刚结束马上又卖出dp[i][2] = dp[i - 1][3] + prices[i]
  • 前一天为持有股票状态(状态1,j = 0),dp[i][2] = dp[i - 1][0] + prices[i]

综上,今天卖掉股票(状态3)的递推公式是:dp[i][2] = max(dp[i - 1][3] + prices[i], dp[i - 1][0] + prices[i]);

综上,今天卖掉股票(状态3)的递推公式是:dp[i][2] = dp[i - 1][0] + prices[i];

处于冷冻期就表明之前的一天一定卖出了股票,因此卖掉股票(即状态3)的前置状态不可能是冷冻期(状态4),刚卖完股票还没买呢没东西可卖

(4)冷冻期dp[i][3]

冷冻期的前置状态只可能是前一天卖出股票(状态3),dp[i][3] = dp[i - 1][2]

总结一下上面三大类,四种状态

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

这就是全部状态的递推公式

3、初始化dp数组

有以下几种情况需要进行初始化

(1)第0天买入股票(状态1)(一定是买入而不是持有,因为第0天不会有前一天的状态延续)

这种情况下肯定初始金钱为0,那么dp[0][0] = -prices[0]

(2)第0天保持不持有状态(状态2)

要找的是dp[0][1]的情况,要在i等于1时讨论,即dp[1][1] = max(dp[0][1], dp[0][3]);

此时dp[0][1]要取0

dp[1][1]指的是第1天保持不持有状态,要在上述二者中取一个最大值

理解1:

那肯定是要使dp[0][3]更大一些才对啊,因为这是冷冻期状态,意味着已经卖过一次股票,手里肯定有钱

故为了不影响dp[0][3]dp[0][1]要取0

理解2:

第0天保持不持有状态 和 第0天冷冻期状态 都是 第1天保持不持有状态 的前置状态,既然最终目的都是要让第1天保持不持有状态,那么其实dp[0][3]dp[0][1]都可以取0,这也解释了dp[0][3]应该初始化为0的原因

(3)第0天卖出股票(状态3)

要找的是dp[0][2]的情况,也要在i等于1时讨论,结果与上面讨论状态2第0天初始化是同理的,dp[0][2]也应该取0

此外,dp[0][3]也初始化为0,见理解2↑

4、确定遍历顺序

从递归公式上可以看出,dp[i] 依赖于 dp[i-1],所以是从前向后遍历。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        //定义dp数组
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));

        //初始化
        dp[0][0] = -prices[0];

        //遍历dp数组
        for(int i = 1; i < prices.size(); ++i){
            //买入股票:
            //维持前一天买入股票的状态
            //前一天是冷冻期(状态4,j = 3),冷冻期一结束马上买入
            //前一天是不持有股票状态(状态2,j = 1),昨天之前就已经卖掉股票并过了冷冻期,但是还没有买入股票,今天买入
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            //不持有股票
            //前一天为冷冻期(状态4,j = 3),两天之前卖掉了股票,经过一天冷冻期到今天
            //前一天就是不持有股票的状态,昨天之前就已经卖掉股票并度过了冷冻期
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];//前一天为持有股票状态(状态1,j = 0)
            dp[i][3] = dp[i - 1][2];//前一天卖出股票(状态3)
        }
        //状态2、3、4都有可能是最大值
        return max(dp[prices.size() - 1][3], max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]));
    }
};

//ACM模式
#include <iostream>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
int maxProfit(vector<int>& prices) {  
    int n = prices.size();  
    if (n == 0) return 0;  
  
    vector<int> dp(n, 0);  
    dp[0] = -prices[0];  
  
    for (int i = 1; i < n; ++i) {  
        dp[i] = max(dp[i-1], max(dp[i-1-3], dp[i-1-1]) - prices[i]); // 买入股票  
        dp[i] = max(dp[i], dp[i-1]); // 不持有股票  
        dp[i] = max(dp[i], dp[i-1]+prices[i]); // 持有股票  
    }  
  
    return max(dp[n-1-3], max(dp[n-1-1], dp[n-1])); // 返回最大值  
}  
  
int main() {  
    vector<int> prices = {7,1,5,3,6,4};  
    int result = maxProfit(prices);  
    cout << "Maximum Profit: " << result << endl;  
    return 0;  
}

状态2---保持不持有状态(已经卖掉股票)

状态3---今天卖掉股票

状态4---冷冻期(卖掉股票才可能进入冷冻期)

为什么返回的是状态状态2、3、4中的最大值,因为这三个状态都卖出了股票,最后卖出股票才有可能得到最大收益

至于为什么状态2、3单独取max?其实无所谓顺序,只是max一次只能输入两个比较值所以要这样写

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

力扣题目链接(opens new window)

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

示例 1:

  • 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
  • 输出: 8

解释: 能够达到的最大利润:

  • 在此处买入 prices[0] = 1
  • 在此处卖出 prices[3] = 8
  • 在此处买入 prices[4] = 4
  • 在此处卖出 prices[5] = 9
  • 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000

思路

与买卖II几乎一样,只是需要加入手续费的处理逻辑即可

再推导一下所有的情况吧

(1)持有股票dp[i][0]

如果是第i天买入的,那么要用没有持有该股票时有的钱减去股票的售价,即dp[i][0] = dp[i - 1][1] - prices[i]

如果是第i-1天买入的,就还是和上一题一样,状态延续到第i天即可,即dp[i][0] = dp[i - 1][0]

综上,dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有

(2)不持有股票dp[i][1]

如果是第i天卖掉的,那就要用持有该股票时有的钱加上卖股票得的钱然后还要减掉手续费,即dp[i][1] = dp[i - 1][0] + prices[i] - fee

如果是第i-1天卖掉的,延续第i天的状态即可,即dp[i][1] = dp[i - 1][1]

综上,dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);//不持有文章来源地址https://www.toymoban.com/news/detail-425263.html

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();//获取prices数组长度(天数)
        vector<vector<int>> dp(n, vector<int>(2, 0));//创建dp数组
        dp[0][0] -= prices[0]; //初始化
        //dp[0][1] = 0;
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);//不持有
        }
        return max(dp[n - 1][0], dp[n - 1][1]);//最后一天要求把股票卖掉,返回不持有股票的最大金钱数
    }
};

到了这里,关于【LeetCode动态规划#13】买卖股票含冷冻期(状态众多,比较繁琐)、含手续费的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【学会动态规划】最佳买卖股票时机含冷冻期(15)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:309. 最佳买卖股票时机含冷冻

    2024年02月14日
    浏览(54)
  • [Leetcode] 买卖股票合集(动态规划)

    写完这套题,再搞一台时光机,财务自由不是梦(Doge) ================================== 相关题目链接 121 买卖股票的最佳时机 122 买卖股票的最佳时机 II 123 买卖股票的最佳时机 III 188 买卖股票的最佳时机 IV 309 买卖股票的最佳时机含冷冻期 714 买卖股票的最佳时机含手续费 给定一

    2023年04月16日
    浏览(47)
  • 【LeetCode】买卖股票的最佳时机含冷冻期

    链接: 买卖股票的最佳时机含冷冻期 题目描述 算法分析 程序设计

    2024年02月13日
    浏览(41)
  • 【动态规划】简单多状态dp问题(2)买卖股票问题

    买卖股票问题 传送门:力扣309. 最佳买卖股票时机含冷冻期 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经

    2024年02月12日
    浏览(56)
  • 动态规划-状态机(188. 买卖股票的最佳时机 IV)

    状态分类: f[i,j,0]考虑前i只股票,进行了j笔交易,目前未持有股票 所能获得最大利润 f[i,j,1]考虑前i只股票,进行了j笔交易,目前持有股票 所能获得最大利润 状态转移: f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i]); f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i]);   还有一位

    2024年02月08日
    浏览(44)
  • 【LeetCode】309. 买卖股票的最佳时机含冷冻期

    给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意: 你不能同时参与

    2024年02月10日
    浏览(44)
  • LeetCode:121.买卖股票的最佳时机——动态规划

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 关于动态规划:LeetCode:322. 零钱兑换——动态规划从案例入门 题目描述 :给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只

    2023年04月17日
    浏览(42)
  • 动态规划 Leetcode 714 买卖股票的最佳时机含手续费

    Leetcode 714 学习记录自代码随想录 要点:1.两种状态持有股票和不持有股票; 2.递推公式 d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] − p r i c e s [ i ] ) d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] + p r i c e s [ i ] − f e e ) dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices

    2024年04月09日
    浏览(47)
  • 【LeetCode动态规划#12】详解买卖股票I~IV,经典dp题型

    力扣题目链接(opens new window) 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最

    2023年04月24日
    浏览(55)
  • 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

    力扣题目链接(opens new window) 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

    2024年01月16日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包