炒股什么时候买进卖出(炒股买进卖出手续费)
通知:我已经将刷题指南全部整理到了Github :https://github.com/youngyangyang04/leetcode-master,方便大家在电脑上阅读,这个仓库每天都会更新,大家快去给一个star支持一下吧!
同时我在B站更新算法视频,B站同名:代码随想录
714.买卖股票的最佳时机含手续费
题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
给定一个整数数组 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.思路
在讲解贪心专题的时候,我们已经讲过本题了贪心算法:买卖股票的最佳时机含手续费
使用贪心算法,的性能是:
时间复杂度:O(n)空间复杂度:O(1)那么我们再来看看是使用动规的方法如何解题。
相对于动态规划:122.买卖股票的最佳时机II,本题只需要在计算卖出操作的时候减去手续费就可以了,代码几乎是一样的。
唯一差别在于递推公式部分,所以本篇也就不按照动规五部曲详细讲解了,主要讲解一下递推公式部分。
这里重申一下dp数组的含义:
dp[i][0] 表示第i天持有股票所省最多现金。dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]所以:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
在来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来
第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金,注意这里需要有手续费了即:dp[i - 1][0] + prices[i] - fee所以:dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
本题和动态规划:122.买卖股票的最佳时机II的区别就是这里需要多一个减去手续费的操作。
以上分析完毕,C++代码如下:
classSolution{public:intmaxProfit(vector<int>&prices,intfee){intn=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));dp[0][0]-=prices[0];//持股票for(inti=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);}returnmax(dp[n-1][0],dp[n-1][1]);}};
时间复杂度:O(n)空间复杂度:O(n)「代码随想录」原创算法学习手册开放下载!
我已经将「代码随想录」中的二叉树、回溯算法、贪心算法、背包问题专题都整理成PDF,绝对精华,绝对通透!
先预览一下部分截图:
无套路,直接给出下载地址:https://pan.baidu.com/s/1smqn0f6xhQNV3NAWw61SHg 密码: vjqw
@代码随想录 期待你的关注