做移动互联网站点,wordpress title背景,代理服务器地址怎么设置,服务商的英文简称题目#xff1a;188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
参考链接#xff1a;代码随想录
188.买卖股票的最佳时机IV
思路#xff1a;本题和上题的最多两次买卖相比#xff0c;改成了最多k次#xff0c;使用类似思路188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
参考链接代码随想录
188.买卖股票的最佳时机IV
思路本题和上题的最多两次买卖相比改成了最多k次使用类似思路需要设计12k个状态第一个不设置也可以。dp五部曲dp数组dp[i][0-2k]dp[i][0]表示无操作dp[i][1]表示第一次持有的最大现金dp[i][2]表示第一次不持有…dp[i][2k-1]表示第k次持有dp[i][2k]表示第k次不持有递推公式类似上题第i天第j次持有时考虑第i-1天持有或不持有dp[i][2j-1]max(dp[i-1][2j-1],dp[i-1][2j-2]-prices[i])第i天第j次不持有时dp[i][2j]max(dp[i-1][2j],dp[i-1][2j-1]prices[i])初始化首先全部初始化为0dp[i][0]始终为0然后dp[0][2j-1]初始化为-prices[0]dp[0][2j]初始化为0类似上题遍历顺序顺序遍历举例略。时间复杂度O(nk)。
class Solution {
public:int maxProfit(int k, vectorint prices) {vectorvectorint dp(prices.size(),vectorint(2*k1,0));for(int j0;jk;j){//初始化dp[0][2*j1]-prices[0];}for(int i1;iprices.size();i){for(int j1;jk;j){//第j次持有和第j次不持有dp[i][2*j-1]max(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);dp[i][2*j]max(dp[i-1][2*j],dp[i-1][2*j-1]prices[i]);}}return dp[prices.size()-1][2*k];}
};注意cpp中数字和字母之间的乘号不能省略否则报错。
309.最佳买卖股票时机含冷冻期
思路本题可以多次买卖加入了一天冷冻期卖出后第二天不能买需要仔细分析状态有四个状态状态一为持有股票然后对于不持有股票的情况要分开讨论状态二为保持卖出股票两天前就卖掉了已经度过冷冻期或者一直就没操作即可以随时买入股票度过了冷冻期状态三为当天卖出股票状态四为冷冻期即前一天卖出股票。如图所示
和前几题相比本题增加了一个今天卖出股票的状态之前都没有因为冷冻期之前一天只能是当天卖出的状态需要和普通的不持有股票状态区分开来。dp五部曲dp数组dp[i][0-4]分别表示持有股票、保持卖出股票、当天卖出股票、冷冻期的最大现金递推公式dp[i][0]持有股票前一天有三种情况首先是本来就持有的dp[i-1][0]然后是冷冻状态或者保持卖出状态下买入dp[i-1][1]-prices[i]dp[i-1][3]-prices[i]取maxdp[i][1]卖出状态前一天要么本来就是保持卖出dp[i-1][1]或者冷冻状态dp[i-1][3]取max注意不是当天卖的故不需要prices[i]dp[i][2]当天卖出前一天必定是持有dp[i][2]dp[i-1][0]prices[i]dp[i][3]冷冻期前一天必定是卖出股票dp[i][3]dp[i-1][2]初始化首先全部初始化为0dp[0][0]-prices[i]dp[0][1]直接思考想不出设置为什么合适所以直接根据递推公式算经过几次递推后必定为0dp[0][2]和dp[0][3]也为0遍历顺序顺序遍历举例略。时间复杂度O(n)。最后返回值为状态1,2,3取max。
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(),vectorint(4,0));dp[0][0]-prices[0];for(int i1;iprices.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[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));}
};714.买卖股票的最佳时机含手续费
思路本题又是无限次交易只不过添加了手续费因此比较容易只需要在交易的时候计算现金的时候减去手续费就OK。dp五部曲dp数组dp[i][0]表示持有股票最大现金dp[i][1]表示不持有股票最大现金递推公式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])初始化dp[0][0]-prices[i]-fee其他都初始化为0遍历顺序顺序遍历举例略。时间复杂度O(n)。手续费在卖的时候扣也可以。
class Solution {
public:int maxProfit(vectorint prices, int fee) {vectorvectorint dp(prices.size(),vectorint{0,0});dp[0][0]-prices[0]-fee;for(int i1;iprices.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][1];}
};
