动态规划的思想。
使用dp[i][0]表示持有股票的最大利润
dp[i][1]表示不持有股票的最大利润
dp[i][0] = max(dp[i-1][0], -price[i])，i-1就持有了，或者在i的时候买入 ，因为只能买入一次，在买入的时候，现金肯定是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];
}
};
算法思想：
动态规划的思想。
不同于上一题的是
dp[i][0]不持有的递归公式是：
dp[i][0] = max(dp[i-1][0], dp[i][1] - 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], 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个状态
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次买卖
算法思想：
动态规划，在买卖2次的基础上进行升级。
用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]); //不持有，上一个状态+卖出的价格
}
}
return dp[prices.size()-1][2*k];
}
};
算法思想：动态规划
dp[i][0] 表示持有股票的状态
dp[i][1]表示冷冻期之后不持有股票的状态
dp[i][2]表示卖出股票的状态,这天就卖出
dp[i][3]表示冷冻期
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i], dp[i-1][2] -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] //冷冻期前一天是卖出的状态
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];//表示持有股票的状态
dp[0][1] = 0; //冷冻期之后，保持卖出的状态
dp[0][2] = 0; //卖出的当天
dp[0][3] = 0; //冷冻期的状态
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]);
}
};
算法思想：
动态规划，在无限次买卖股票的基础上加上一个手续费的操作。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
//在买卖股票无限次的基础上加上手续费的操作
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];
}
};
