代码随想录训练营Day 53|力扣309.最佳买卖股票时机含冷冻期 、714.买卖股票的最佳时机含手续费、总结

本文主要是介绍代码随想录训练营Day 53|力扣309.最佳买卖股票时机含冷冻期 、714.买卖股票的最佳时机含手续费、总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

代码随想录

代码:

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(4,0)); // 因为冷冻期是在卖出股票的后一天,所以必须指出是哪一天卖出了股票,也就是我们要把这个状态单独定义出来// dp[i][0] 第i天持有股票的最大利润// dp[i][1] 第i天保持卖出股票的最大利润// dp[i][2] 第i天当天卖出股票的最大利润// dp[i][3] 第i天为冷冻期dp[0][0] = -prices[0];int n = prices.size();for(int i = 1; i < prices.size(); i++){// 持有股票:前一天就持有了 或 前一天已经过了冷冻期,今天买入股票 或 前一天就是冷冻期,今天买入股票dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1] - prices[i] ,dp[i - 1][3] - prices[i]));// 保持卖出股票:前一天就已经保持卖出股票了 或 前一天是冷冻期dp[i][1] = 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 max(dp[n - 1][3], max(dp[n - 1][2], dp[n - 1][1]));}
};

 思路:

        dp数组的含义:dp[i][0] 第i天持有股票的最大利润;dp[i][1] 第i天保持卖出股票的最大利润;dp[i][2] 第i天当天卖出股票的最大利润;dp[i][3] 第i天为冷冻期的最大利润。

(因为冷冻期是在卖出股票的后一天,所以必须指出是哪一天卖出了股票,也就是我们要把这个状态单独定义出来。)

        dp数组的递推公式:

             // 持有股票:前一天就持有了 或 前一天已经过了冷冻期,今天买入股票 或 前一天就是冷冻期,今天买入股票

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

            // 保持卖出股票:前一天就已经保持卖出股票了 或 前一天是冷冻期

            dp[i][1] = 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];

        dp数组的初始化: 将dp[0][0]初始化为-prices[0]。这几道买卖股票的题都是把第0天买入股票的情况初始化为-prices[0]

        dp数组的遍历顺序:后一天的状态依赖于前一天的状态,正序遍历。

细节:我在最后返回值的时候,知道max在比较三个数的时候要嵌套着用了,但是我忘记了递推公式里持有股票也是比较三个值。。。

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

视频讲解:动态规划来决定最佳时机,这次含手续费!| LeetCode:714.买卖股票的最佳时机含手续费_哔哩哔哩_bilibili

代码随想录

代码:

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>>dp(n,vector<int>(2,0));// dp[i][0] 第i天持有股票的最大利润// dp[i][1] 第i天不持有股票的最大利润dp[0][0] = -prices[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 dp[n - 1][1];}
};

 思路:

        dp数组的含义:dp[i][0] 第i天持有股票的最大利润;dp[i][1] 第i天不持有股票的最大利润

        dp数组的递推公式:注意手续费是在卖出股票时付 !!

             // 持有股票: 前一天就持有 或 前一天不持有,今天买入

            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);

        dp数组的初始化: 将dp[0][0]初始化为-prices[0]。这几道买卖股票的题都是把第0天买入股票的情况初始化为-prices[0]

        dp数组的遍历顺序:后一天的状态依赖于前一天的状态,正序遍历。 

3.总结

        买卖股票问题大致遇到这么几类:

        

共同点就是: 这几道买卖股票的题都是把第0天买入股票的情况初始化为-prices[0]

这篇关于代码随想录训练营Day 53|力扣309.最佳买卖股票时机含冷冻期 、714.买卖股票的最佳时机含手续费、总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044085

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;