买卖股票的最佳时机三 全球观点
2023-06-05 09:44:34
个人图书馆-激流一舟
导读 ^_^
买卖股票的系列问题三！这回的限制是全局最多能买卖两次操作。
(资料图片)
题目
leetcode 123
代码与思路
注意：这里的2次是最多两次
确定dp数组以及下标的含义
dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
没有操作
第一次买入
第一次卖出
第二次买入
第二次卖出
递归公式
dp[i][1]状态，有两个具体操作：
操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
dp[i][2]也有两个操作：
操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
同理可推出剩下状态部分：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]);
//买卖股票最佳时机IIIclassSolution{public:intmaxProfit(vector&prices){if(prices.size()==0)return0;vector>dp(prices.size(),vector(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];//相当于第0天买入买出，再买入for(inti=1;i 
