動態(tài)規(guī)劃的思想遍膜。
使用dp[i][0]表示持有股票的最大利潤
dp[i][1]表示不持有股票的最大利潤
dp[i][0] = max(dp[i-1][0], -price[i])扩所，i-1就持有了忱辅，或者在i的時候買入 搔耕，因為只能買入一次隆判，在買入的時候举哟，現(xiàn)金肯定是0
dp[i][1] = max(dp[i-1][0], dp[i-1][0] + prices[i])
class Solution {
public:
? ? int maxProfit(vector<int>& prices) {
? ? ? ? vector<vector<int>> dp(prices.size(), vector<int>(2));
? ? //? dp[i][0] 表示持有； dp[i][1]表示不持有
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? dp[0][0] = -prices[0];
? ? ? ? dp[0][1] = 0;
? ? ? ? for(int i=1;i<prices.size();i++)
? ? ? ? {
? ? ? ? ? ? dp[i][0] = max(dp[i-1][0], -prices[i]); // 這里的prices[i]為什么不是dp[i-1][1]-prices[i]
? ? ? ? ? ? dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
? ? ? ? }
? ? ? ? return dp[prices.size()-1][1];
? ? }
};
算法思想：
動態(tài)規(guī)劃的思想馍忽。
不同于上一題的是
dp[i][0]不持有的遞歸公式是：
dp[i][0] = max(dp[i-1][0], dp[i][1] - prices[i]) 。因為可以買賣多次燕差，在買入的時候遭笋，現(xiàn)金由上一個狀態(tài)決定
class Solution {public:
? ? int maxProfit(vector<int>& prices) {
? ? ? ? vector<vector<int>>dp(prices.size(), vector<int>(2));
? ? ? ? //dp[i][0]表示持有這只股票
? ? ? ? //dp[i][1]表示不持有
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? dp[0][0] = -prices[0];
? ? ? ? dp[0][1] = 0;
? ? ? ? for(int i=1;i<prices.size();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]);//不持有
? ? ? ? }
? ? ? ? return dp[prices.size()-1][1];
? ? }?
};
算法思想：
需要定義5個狀態(tài)
dp[i][0]表示不操作（沒什么用）
dp[i][1]表示第一次持有
dp[i][2]表示第一次不持有
dp[i][3]表示第二次持有
dp[i][4]表示第二次不持有
遞推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], -prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1[2] - prices[i]])
dp[i][3] = max(dp[i-1][4], dp[i-1][3] + prices[i])
class Solution {
public:
? ? int maxProfit(vector<int>& prices) {
? ? ? ? vector<vector<int>> dp(prices.size(), vector<int>(5));
? ? ? ? dp[0][0] = 0;
? ? ? ? dp[0][1] = -prices[0];
? ? ? ? dp[0][2] = 0;
? ? ? ? dp[0][3] = -prices[0];
? ? ? ? dp[0][4] = 0;
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? for(int i=1;i<prices.size();i++)
? ? ? ? {
? ? ? ? ? ? dp[i][0] = dp[i-1][0];
? ? ? ? ? ? dp[i][1] = max(dp[i-1][1], -prices[i]) ;
? ? ? ? ? ? dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]);//第一次持有+賣出的價格
? ? ? ? ? ? dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]); //第一次持有賣出的加入-第二次買入的價格
? ? ? ? ? ? dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]); //第二次持有的價格-第二次賣出的價格
? ? ? ? }
? ? ? ? return dp[prices.size()-1][4];
? ? }
};
可以進行k次買賣
算法思想：
動態(tài)規(guī)劃，在買賣2次的基礎(chǔ)上進行升級徒探。
用j表示可以買賣第幾次瓦呼。那j最大等于2k
dp[i][j] 不操作，表示dp[i][j+1] 表示持有测暗，dp[i][j+2]表示不持有
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] -prices[i]
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
class Solution {
public:
? ? int maxProfit(int k, vector<int>& prices) {
? ? ? ? vector<vector<int>> dp(prices.size(), vector<int>(2*k+1));
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? //初始化
? ? ? ? for(int j=0;j<2*k-1;j+=2)
? ? ? ? {
? ? ? ? ? ? dp[0][j] =0;
? ? ? ? ? ? dp[0][j+1]= -prices[0];
? ? ? ? }
? ? ? ? for(int i=1;i<prices.size();i++)
? ? ? ? {
? ? ? ? ? ? for(int j=0;j<2*k-1;j+=2)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? // cout<<"j:"<<j<<endl;
? ? ? ? ? ? ? ? dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
? ? ? ? ? ? ? ? dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]); //不持有央串，上一個狀態(tài)+賣出的價格
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[prices.size()-1][2*k];
? ? }
};
算法思想：動態(tài)規(guī)劃
dp[i][0] 表示持有股票的狀態(tài)
dp[i][1]表示冷凍期之后不持有股票的狀態(tài)
dp[i][2]表示賣出股票的狀態(tài),這天就賣出
dp[i][3]表示冷凍期
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i], dp[i-1][2] -prices[i])// 前一天持有股票磨澡，前一天是冷凍期之后不再持有的狀態(tài)然后當(dāng)前買入，前一天是冷凍期買入
dp[i][1] = max(dp[i-1][1], dp[i-1]3[])//前一天是不再持有质和，或者是冷凍期
dp[i][2] = dp[i-1][0] + prices[i] //前一天是持有的狀態(tài)
dp[i][3] = dp[i-1][2] //冷凍期前一天是賣出的狀態(tài)
class Solution {
public:
? ? int maxProfit(vector<int>& prices) {
? ? ? ? vector<vector<int>> dp(prices.size(), vector<int>(4,0));
? ? ? ? //初始化
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? dp[0][0] = -prices[0];//表示持有股票的狀態(tài)
? ? ? ? dp[0][1] = 0; //冷凍期之后稳摄，保持賣出的狀態(tài)
? ? ? ? dp[0][2] = 0; //賣出的當(dāng)天
? ? ? ? dp[0][3] = 0; //冷凍期的狀態(tài)
? ? ? ? for(int i=1;i<prices.size();i++)
? ? ? ? {
? ? ? ? ? ? dp[i][0] = max(max(dp[i-1][0], 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(max(dp[prices.size()-1][1], dp[prices.size()-1][2]), dp[prices.size()-1][3]);
? ? }
};
算法思想：
動態(tài)規(guī)劃，在無限次買賣股票的基礎(chǔ)上加上一個手續(xù)費的操作饲宿。
class Solution {
public:
? ? int maxProfit(vector<int>& prices, int fee) {
? ? ? ? //在買賣股票無限次的基礎(chǔ)上加上手續(xù)費的操作
? ? ? ? vector<vector<int>> dp(prices.size(), vector<int>(2,0));
? ? ? ? if(prices.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? dp[0][0] = -prices[0]; //持有
? ? ? ? dp[0][1] = 0; //不持有
? ? ? ? for(int i=1;i<prices.size();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[prices.size()-1][1];
? ? }
};
