【动态规划】买卖股票问题

1.一次买入，一次卖出

买卖股票1

1.明确dp[i][0] dp[i][1]含义

dp[i][0]:表示可能在前i天(包括第i天)不持有该股票,产生的最大收益

dp[i][1]:表示可能在前i天(包括第i天)持有该股票,产生的最大收益

2.递推公式

dp[i][0]可能在i天之前卖出，所以的dp[i][0]保持收益，dp[i][0]=dp[i-1][0];

dp[i][0]也可能在第i天卖出，此时dp[i][0]保持最大收益的话，需要在i天之前未卖出产生的最大收益dp[i-1][1]+第i天卖出的收益prices[i].

因为要取dp[i][0]的最大收益，所以

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

dp[i][1]可能i天之前已经买入，所以的dp[i][1]保持收益，dp[i][1]=dp[i-1][1];

也可能在第i天买入，则前i天需要未持有股票dp[i-1][0]的最大收益（0）+第i天才买入的收益-prices[i].，由于只能是一次买入，所以不用+前面的前i天需要未持有股票dp[i-1][0]的最大收益（与类型二的区别）

因为要取dp[i][1]的最大收益，所以

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

3.初始化

dp[0][0]:表示下标为0开始就不持有该股票最大收益为0，没买股票当然是0

dp[0][1]:表示下标为0开始持有该股票最大收益为-prices[i]

dp[0][0]=0;
dp[0][1]-=prices[0];

4.遍历

根据递推公式发现先要初始化前面的值，所以从前到后,dp二维数组的第一个下标范围是股票数组的下标范围，因为0已经初始化，所以从1开始

5.代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
 vector<vector<int>>dp(prices.size()+1,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],-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]);//返回最大值
    }
};

2.任意买入，任意卖出

买卖股票2

1.明确dp[i][0] dp[i][1]含义

dp[i][0]:表示可能在前i天(包括第i天)不持有该股票,产生的最大收益

dp[i][1]:表示可能在前i天(包括第i天)持有该股票,产生的最大收益

2.递推公式

dp[i][0]可能在i天之前卖出，所以的dp[i][0]保持收益，dp[i][0]=dp[i-1][0];

dp[i][0]也可能在第i天卖出，此时dp[i][0]保持最大收益的话，需要在i天之前未卖出产生的最大收益dp[i-1][1]+第i天卖出的收益prices[i].

因为要取dp[i][0]的最大收益，所以

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

dp[i][1]可能i天之前已经买入，所以的dp[i][1]保持收益，dp[i][1]=dp[i-1][1];

==也可能在第i天买入，则前i天需要未持有股票dp[i-1][0]的最大收益+第i天才买入的收益

-prices[i].==因为要取dp[i][1]的最大收益，所以

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

3.初始化

dp[0][0]:表示下标为0开始就不持有该股票最大收益为0，没买股票当然是0

dp[0][1]:表示下标为0开始持有该股票最大收益为-prices[i]

dp[0][0]=0;
dp[0][1]-=prices[0];

4.遍历

根据递推公式发现先要初始化前面的值，所以从前到后,dp二维数组的第一个下标范围是股票数组的下标范围，因为0已经初始化，所以从1开始

5.代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
   vector<vector<int>>dp(prices.size()+1,vector<int>(2));
  dp[0][0]=0;
  dp[0][1]-=prices[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 max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
    }
};

3.最多两次买入

买卖股票3

1.明确dp[i][0] dp[i][1] dp[i][2] dp[i][3] dp[i][4]

dp[i][0]:表示前i次包括i无操作,产生的最大收益

dp[i][1]:表示前i次包括i第一次持有股票,产生的最大收益

dp[i][2]:表示前i次包括i第一次卖出股票,产生的最大收益

dp[i][3]:表示前i次包括i第二次持有股票,产生的最大收益

dp[i][4]:表示前i次包括i第二次卖出股票,产生的最大收益

2.递推公式

dp[i][0]如果前i天无操作的话，即不买卖股票，dp[i][0]=dp[i-1][0];

dp[i][1]分两个状态，前i天的某一次第一次持有股票，则dp[i][1]=dp[i-1][1]

第i天第一次持有股票，则需要前i天无操作dp[i-1][0]-第i天买入股票prices[i]

然后取两个状态的最大收益的最大收益

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

dp[i][2]可能在前i-1天已经第一次卖出股票dp[i][2]=dp[i-1][2];

也可能在第i天第一次卖出股票，但是要保证前i-1天的某一天第一次持有股票dp[i-1][1]

+第i天第一次卖出股票的收益prices[i].然后取两个状态的最大收益的最大收益

dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);

dp[i][3]可能在前i-1天已经第二次持有股票dp[i][3]=dp[i-1][3];

可能是第i天才第二次持有股票,但是必须在前i-1天的某一天第一次卖出股票dp[i-1][2]-第i天第二次买股票prices[i]; dp[i][3]=dp[i-1][2]-price[i];

然后取两个状态的最大收益的最大收益

dp[i][3]=max(dp[i-1][3],dp[i-1][2]-price[i]);

dp[i][4]可能在前i-1天已经第二次卖出股票dp[i][4]=dp[i-1][4];

也可能在第i天才第二次卖出股票，但是要保证在前i-1天的某一天第二次持有股票dp[i-1][3],dp[i][4]=dp[i-1][3]+prices[i];

然后取两个状态的最大收益的最大收益

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

3.初始化

dp[0][0]=0;//第0天无操作收益为0
dp[0][1]=-price[0];//第0天第一次买入股票收益-price[0]
dp[0][2]=0;//第0天第一次卖出股票可以理解为在一天内买入股票，再卖出股票收益为0
dp[0][3]=-price[0];//第0天第二次买入股票收益-price[0]
dp[0][4]=0;//第0天第二次卖出股票收益为0，在同一天买入卖出同一只支票，收益为0

4.遍历

根据递推公式发现先要初始化前面的值，所以从前到后,dp二维数组的第一个下标范围是股票数组的下标范围，因为0已经初始化，所以从1开始

5.代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>>dp(prices.size()+1,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;
        for(int i=1;i<prices.size();i++)
            {
               dp[i][0]=dp[i-1][0];//无操作
               dp[i][1]=max(dp[i-1][1],dp[i-1][0]-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];
    }
};

4.最多k次买入

该题型和题型3一样

买卖股票4

1.dp[][]含义与题型三相同

2.递推公式

需要k次买入，k次卖出。

使用循环搞定递推公式

for(int j=0;j<2*k;j+=2)
{
dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);//第j+1次已入
dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);//第j+1次卖出
}

j=0;代表第一次

3.初始化

根据题型3，我们发现每次在买入收益会-price[0]；在同一次卖出时在vector中我们会初始化为0

for(int i=1;i<2*k;i+=2)
{
dp[0][i]=-prices[0];
}

4.遍历

for(int i=1;i<prices.size();i++)
            for(int j=0;j<2*k;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]);
               
          
            
            }

5.代码实现

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    
vector<vector<int>>dp(prices.size()+1,vector<int>(2*k+1,0));
for(int i=1;i<=2*k;i+=2)
{dp[0][i]=-prices[0];}
           for(int i=1;i<prices.size();i++)
            for(int j=0;j<2*k;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]);
               
          
            
            }
             
    return  dp[prices.size()-1][2*k];
    }
};

5.买卖股票含冷冻期

买卖股票冻结期

1.dp[i][0] dp[i][1] dp[i][2] dp[i][3] 的含义

dp[i][0]:表示第i天持有股票,产生的最大收益

dp[i][1]:表示第i天保持卖出股票,产生的最大收益

dp[i][2]:表示第i天卖出股票,产生的最大收益

dp[i][3]:表示第i天出现冻结期,产生的最大收益

2.递推公式

dp[i][0]可能在前i-1天持有股票，收益维持dp[i][0]=dp[i-1];

可能是第i天才买入股票，这种情况分为第i-1天是冷冻期，或者第i-1天是保持卖出股票的状态dp[i][0]=max(dp[i-1][3],dp[i-1][1]);

然后取两个状态的最大收益的最大收益

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

dp[i][1] 第i-1天可能也是保持卖出股票dp[i][1]=dp[i-1][1];

第i-1天可能是冻结期dp[i][1]=dp[i-1][3];

然后取两个状态的最大收益的最大收益

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

dp[i][2]第i天卖出股票说明i-1天持有股票+第i天卖出股票

dp[i][2]=dp[i-1][0]+prices[i];

dp[i][3]第i天出现冻结期，则前一天是卖出股票的，dp[i][3]=dp[i-1][2];

3.初始化

dp[0][0]=-price[0]//第0天持有股票
dp[0][2]=0//第0天卖出股票，同一天买入卖出则收益为0
dp[0][1]=0;//第0天出现保持卖出状态，举例你一天内已经买入卖出，此时就是保持卖出状态收益为0，这只是举个例子，这个其实现实中没意义
dp[0][3]=0//...第0天卖出即进入冻结状态，收益也是0，这只是举个例子，这个其实现实中没意义

4.遍历

根据递推公式发现先要初始化前面的值，所以从前到后,dp二维数组的第一个下标范围是股票数组的下标范围，因为0已经初始化，所以从1开始

5.代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        if(prices.size()==0)return 0;
        vector<vector<int>>dp(prices.size()+1,vector<int>(4,0));
        dp[0][0]-=prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<prices.size();i++)
           {
        dp[i][0]=max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
        dp[i][1]=max(dp[i-1][3],dp[i-1][1]);
        dp[i][2]=dp[i-1][0]+prices[i];
        dp[i][3]=dp[i-1][2];
 }
           return max(dp[prices.size()-1][2],max(dp[prices.size()-1][1],dp[prices.size()-1][3]));//当还持有股票时不会是最大收益，排除一种
    }
};

6.买卖股票有手续费（与题型二相似）

#股票问题手续费

1.明确dp[i][0] dp[i][1]含义

dp[i][0]:表示可能在前i天(包括第i天)不持有该股票,产生的最大收益

dp[i][1]:表示可能在前i天(包括第i天)持有该股票,产生的最大收益

2.递推公式

dp[i][0]可能在i天之前卖出，所以的dp[i][0]保持收益，dp[i][0]=dp[i-1][0];

dp[i][0]也可能在第i天卖出，此时dp[i][0]保持最大收益的话，需要在i天之前未卖出产生的最大收益dp[i-1][1]+第i天卖出的收益prices[i].

因为要取dp[i][0]的最大收益，所以

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

dp[i][1]可能i天之前已经买入，所以的dp[i][1]保持收益，dp[i][1]=dp[i-1][1];

==也可能在第i天买入，则前i天需要未持有股票dp[i-1][0]的最大收益+第i天才买入的收益

-prices[i].==因为要取dp[i][1]的最大收益，所以

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

因为每次买卖同一只股票收取一次手续费，则我们可以将手续费夹在买入或者卖出时

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee); // ppppppppppp dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

或

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]); // ppppppppppp dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);

3.初始化

dp[0][0]:表示下标为0开始就不持有该股票最大收益为0，没买股票当然是0

dp[0][1]:表示下标为0开始持有该股票最大收益为-prices[i]

dp[0][0]=0;
dp[0][1]-=prices[0];

4.遍历

根据递推公式发现先要初始化前面的值，所以从前到后,dp二维数组的第一个下标范围是股票数组的下标范围，因为0已经初始化，所以从1开始

5.代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
    vector<vector<int>>dp(prices.size(),vector<int>(2));
    dp[0][0]=0;
    dp[0][1]=-prices[0];
    
    for(int i=1;i<prices.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][0];
     
    }
};