121. 买卖股票的最佳时机
这题和贪心中的买股票很想,但这里不用考虑局部问题,因为只用买一张卖一张。
我想可以用一个数组dp来记录买入价格和卖出价格。
然后遍历数组
草我感觉我写的想贪心。
动态规划
dp[i][0]表示第i天不持股的最大收益,dp[i][1]表示第i天持股的最大收益。dp[i][1]实际上是负数,因为股票还没卖出去。
dp[i][0]可以由由dp[i-1][1]+prices[i]推到而来,也可以是dp[i-1][0]推导而来,应该取一个最大值。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
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],-prices[i]);
//要么是延续前一天持股的状态,要么是才买入。
//由于股票只能买一次,所以并不用考虑前面没有持股的状态。
}
return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
}
};
122.买卖股票的最佳时机II
唯一的区别就是在第i天持有股票时,可以是直接继承[i-1][1],还能是当天买入,在上一题中,由于只能买一次,所以买入时手上的最大利润是0,0-prices[i],但这题可以买卖多次,变成了dp[i-1][0]-prices[i]
123.买卖股票的最佳时机III
变成了最多买卖两只股票,且不能同时拥有两只。
变成五个状态了
0:不操作
1:第一次持有股票。
2:第一次有股票后不持有股票。
3:第二次有股票。
4:第二次有股票后不持有股票
注意第一天的股票也要初始化dp[0][3]
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];
for(int i=1;i<prices.size();i++){
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 max(dp[prices.size()-1][2],dp[prices.size()-1][4]);
标签:买卖,股票,最佳时机,max,prices,dp,size
From: https://blog.csdn.net/wwwgxd/article/details/142100260