题目：121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III
参考链接：代码随想录
121. 买卖股票的最佳时机
思路：本题的首想方法就是暴力算法，时间复杂度O(n^2)。然后是贪心算法，左边找最小，然后逐渐往右遍历，取利润最大值即可，时间复杂度O(n)。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low=INT_MAX;
int ans=0;
for(int i=0;i<prices.size();i++){
if(prices[i]<low){
low=prices[i];
}
else if(prices[i]-low>ans){
ans=prices[i]-low;
}
}
return ans;
}
};
股票类题目是典型的dp，但如果没接触到dp数组还不太好想。使用dp五部曲：dp数组，这里如果用dp[i]表示第i天买入最大利润，会发现这个利润是无法算出的，因为还要考虑卖出的日期，要保证状态转移能够完成，考虑第i天的情况，每一天对股票都有两种情况，持有或者不持有，注意持有不是买入，故dp[i][0]表示第i天持有股票所得的最大现金，dp[i][1]表示第i天不持有股票所得的最大现金，初始现金为0；递推公式，如果第i天持有股票，有两种情况，如果i-1天已经持有了，dp[i][0]=dp[i-1][0]，如果是第i天买入，则之前的现金都为0，则dp[i][0]=-price[i]，dp[i][0]取max，如果第i天不持有，也有两种情况，如果第i-1天已经不持有，不管是还没买入还是已经卖掉了，dp[i][1]=dp[i-1][1]，如果第i-1天已经持有，则说明第i天将股票卖掉，dp[i][1]=dp[i][0]+price[i]，dp[i][1]取max；初始化，dp[0][0]=-price[0]，dp[0][1]=0，其他都不需要初始化，由递推公式可知i全部由i-1推导出来，我们就全初始化为0即可；遍历顺序，从左到右；举例略。最终所求的最大利润即为dp[n][1]，因为当天不持有股票一定比持有股票多。时间复杂度O(n)。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>{0,0});
dp[0][0]=-prices[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 dp[prices.size()-1][1];
}
};
虽然时间复杂度相同，但运行时间dp比ga长了许多。还可以使用滚动数组降低空间复杂度，因为只要记录今天和前一天的现金，这里略。
122.买卖股票的最佳时机II
思路：本题和上一题的区别是可以多次购买和出售，之前用ga做过，就是把所有的上升坡度全部加起来，一次遍历就行，时间复杂度O(n)。用dp方法，dp五部曲：dp数组，和上一题差不多，dp[i][0]表示第i天持有股票的最大现金，dp[i][1]表示第i天不持有股票的最大现金；递推公式，这里就和上题有区别了，对dp[i][0]，如果第i天持有，有两种情况，首先是i-1天也持有，这时没有变化，dp[i][0]=dp[i-1][0]，然后是i-1天不持有，即为第i天买入股票，此时的现金还要加上前面的利润，故dp[i][0]=dp[i-1][1]-prices[i]，取max，如果第i天不持有，这里和上题一样，dp[i][1]=max(dp[i-1][1]，dp[i-1][0]+prices[i])；初始化，dp[0][0]=-prices[0]，dp[0][1]=0，其他都为0；遍历顺序为从左到右；举例略。时间复杂度O(n)。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>{0,0});
dp[0][0]=-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 dp[prices.size()-1][1];
}
};
123.买卖股票的最佳时机III
思路：本题又增加了难度，至多进行两次买卖，故状态较多，需要仔细设计dp数组。dp五部曲：dp数组，每一天有五个状态，无操作、第一次持有、第一次不持有、第二次持有、第二次不持有，第二维需要设计五个参数dp[i][0-4]，每一个状态都表示最大现金；递推公式，无操作时，dp[i][0]=0，而且是始终为0，故这个状态其实可以不考虑；第一次持有，有两种情况，首先是前一天未持有，则第i天买入，dp[i][1]=dp[i-1][0]-prices[i]，如果前一天持有，保持不变，dp[i][1]=dp[i-1][1]，取最大值；第一次不持有，有两种情况，首先是前一天持有，说明第i天卖掉，dp[i][2]=dp[i-1][1]+prices[i]，然后是前一天未持有，保持不变，dp[i][2]=dp[i-1][2]，取max；第二次持有，同理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])；初始化，dp[i][0]=0，dp[0][1]=-prices[0]，dp[0][2]=0，表示当天买入后又卖出，dp[0][3]=-prices[i]，dp[0][4]=0，其他都初始化为0；遍历顺序，顺序遍历；举例略。最后返回答案为dp[n-1][4]。时间复杂度O(n)。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>{0,0,0,0,0});
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];
for(int i=1;i<prices.size();i++){//递推从1开始
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];
}
};
本题的关键就是设计状态，写出状态转移。总结这几题可以看到股票类题目就是把持有股票的情况设置为状态，如果有多次买入卖出，每一次都要单独设计状态。