注意:这里面dp[①][②][③]的理解
①第几天
②还剩几次交易机会
③1：当前持股； 0：当前不持股
1.dp的含义是当前这个状态下能达到的最大的收益
2.因为是状态转移，所以已经满足了不会连续买入
3.也因为是状态转移，所以情况多了后，初始化为0位造成影响，比如dp[i][0][0]这个时候是没有持股，并且没有再买入的机会，这个时候若直接用max(dp[i-1][0][0],dp[i-1][0][1]+prices[i]);会是0+prices[i]就会造成误判，所以要初始化为int_min
4.只买一次max(dp[i-1][1],-prices[i]);
无穷次max(dp[i-1][1],dp[i-1][0]-prices[i]);
1.买卖股票的最佳时机
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp[1000010][2];
int max_profit=0;
for(int i=0;i<prices.size();i++){
if(i==0){
dp[i][0]=0;
dp[i][1]=-prices[i];
}
else{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
//写成-prices[i]保证了计算出来的利润只包含了一次的买卖
dp[i][1]=max(dp[i-1][1],-prices[i]);
//cout<<i<<":"<<dp[i][0]<<" "<<dp[i][1]<<endl;
}
}
for(int i=0;i<prices.size();i++){
//对卖出所赚的钱进行比较
max_profit=max(max_profit,dp[i][0]);
}
return max_profit;
}
};2.买卖股票的最佳时机 II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp[100010][2];//[天数][是否持有]
if(prices.size()==0) return 0;
for(int i=0;i<prices.size();i++){
if(i==0){
//初始化
dp[i][0]=0;
dp[i][1]=-prices[i];
}
else{
//状态变换
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
//因为可以交易无限次，所以这里写成dp[i-1][0]-prices[i]
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
}
return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
}
};3.买卖股票的最佳时机 III
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
//注意:应该将初始dp值设为int_min,不然有的第二次卖出是用一个空的状态(0)+prices[i](实际上在这之前根本没买)
vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(3,vector<int>(2,INT_MIN)));
int max_profit=0;
for(int i=0;i<prices.size();i++){
if(i==0){
dp[i][2][0]=0;
dp[i][1][1]=-prices[i];
}
else{
//每当买入才进行一次k--，所以在持股到卖出的这个过程中不用考虑k的变化
//没有买入
//dp[i][2][0]=0;
//第一次卖出
dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
//第二次卖出
if(i>2) dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1]+prices[i]);
//第一次买入
dp[i][1][1]=max(dp[i-1][1][1],-prices[i]);
//第二次买入
if(i>=2) dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][0]-prices[i]);
}
//cout<<i<<":"<<dp[i][1][0]<<" "<<dp[i][0][0]<<" "<<dp[i][1][1]<<" "<<dp[i][0][1]<<endl;
}
//交易一次和交易两次
max_profit=max(dp[prices.size()-1][0][0],dp[prices.size()-1][1][0]);
//不交易
max_profit=max(max_profit,0);
return max_profit;
}
};若是允许k次交易
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
//注意:应该将初始dp值设为int_min,不然有的第二次卖出是用一个空的状态(0)+prices[i](实际上在这之前根本没买)
vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(3,vector<int>(2,0)));
int max_profit=0;
for(int i=0;i<prices.size();i++){
//注意这个初始化!!
for(int j=1;j>=0;j--){
if(i==0){
dp[i][j][0]=0;
dp[i][j][1]=-prices[i];
}
else{
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j+1][0]-prices[i]);
}
}
}
//交易一次和交易两次
max_profit=max(dp[prices.size()-1][0][0],dp[prices.size()-1][1][0]);
//不交易
max_profit=max(max_profit,0);
return max_profit;
}
};4.最佳买卖股票时机含冷冻期
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
int max_profit=0;
for(int i=0;i<prices.size();i++){
if(i==0){
dp[i][0]=0;
dp[i][1]=-prices[i];
}
else{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
if(i>=2) dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);
//若在第二个之前持有股票那么就只可能在0处买或在1处买
else dp[i][1]=max(dp[i-1][1],-prices[i]);
}
}
return dp[prices.size()-1][0];
}
};