LeetCode123.买卖股票的最佳时机III
本题的关键是确定dp数组的含义,由于最多进行两次买卖,所以将dp数组分为五个状态:
dp[i][0]第i天未持有;
dp[i][1]第i天第一次持有;
dp[i][2]第i天第一次未持有;
dp[i][3]第i天第二次持有;
dp[i][4]第i天第二次未持有。
注意这里面持有,包含两个状态,即前一天已经持有或者该天刚刚买入。
返回时返回dp[][4]即可,因为第二次卖出的情况已经包含了第一次卖出的情况,因为对于第一次卖出而言,我还可以在当天再买入再卖出,对于总利润是不变的。
代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),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<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]);
}
int max = INT_MIN;
for(int i=0;i<5;i++){
if(dp[prices.size()-1][i]>max) max = dp[prices.size()-1][i];
}
return max;
}
};
LeetCode188.买卖股票的最佳时机IV
上一题的拓展,每多一次至多买卖,就增加两个状态,再多添加一个for循环遍历每一个状态即可。
代码如下:
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));
for(int i=1;i<2*k+1;i+=2){
dp[0][i] = -prices[0];
}
for(int i=1;i<prices.size();i++){
for(int j=0;j<2*k+1;j++){
if(j==0) dp[i][j] = dp[i-1][j];
else if(j%2==1){
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
}else{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
}
}
}
return dp[prices.size()-1][2*k];
}
};