121. 买卖股票的最佳时机
思路：
每一天有两种状态，持有或者不持有，所以这里用二维数组来表示，dp[i][0]：第i天持有股票时最大的现金数，dp[i][1]：第i天不持有股票时最大的现金数。递推关系：当i天持有股票时，1、第i-1天持有的股票，但是没有卖出dp[i-1][0]，2、第i天新买的股票，因为股票只能买卖一次所以是0-price[i]，二者的最大值为dp[i][0]。当第i天不持有股票时，1、第i-1天就没有股票dp[i-1][1]，2、第i天才卖掉的股票dp[i-1][0]+price[i]，二者取最大值。3、初始化：dp[0][0]=-price[0]，dp[0][1]=0。遍历顺序：从小到大。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>> dp(len,vector<int>(2));
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;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[len-1][1];
}
};
122. 买卖股票的最佳时机 II
思路：
这道题和上一题的区别在于本题可以多次买卖股票，所以递推关系中第i天持有的最大现金数的第二种情况：第i-1天没有持有，第i天才持有时为dp[i-1][1]-price[i]，其他的与上题保持一致。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>> dp(len,vector<int>(2));
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;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[len-1][1];
}
};
123. 买卖股票的最佳时机 III
思路：
这道题的难点在于最多可以有两笔交易，但是两笔交易不能同时持有（例如持有两张股票）。这道题还是沿用上一道题的思路，dp[i][j]:在第j种情况下第i天所持有的最大现金数为dp[i][j]，这里j有5种情况：1、不操作、2、第一次买入、3、第一次卖出、4、第二次买入、5、第二次卖出。递推关系：dp[i][1]:表示第i天第一次持有，有两种情况：1、前一天没有持有，第i天买入dp[i-1][0]-prices[i]；2、前一天持有dp[i-1][1]，二者取最大值。dp[i][2]:表示第i天第一次不持有，有两种情况：1、第i天卖出dp[i-1][1]+prices[i]；2、前一天不持有，今天依旧不持有dp[i-1][2]，二者取最大值。同理可得dp[i][3]、dp[i][4]。初始化：dp[0][0]=0、dp[0][1]=-prices[0]、dp[0][2]=0(这里可以理解为当天买了又卖了)，dp[0][3]=-prices[0]（这里可以理解为当天买了又卖了然后又买了），dp[0][4]=0。遍历顺序：从小到大。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>> dp(len,vector<int>(5,0));
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<len;i++)
{
dp[i][0]=0;
dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1]);
dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2]);
dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3]);
dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4]);
}
return max(dp[len-1][2],dp[len-1][4]);
}
};
