Day50 | 123.买卖股票的最佳时机III, 188.买卖股票的最佳时机IV
买卖股票的最佳时机III
LeetCode题目:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
买卖股票的最佳时机问题III,此时要求最多购买两次股票。因此对股票的递推公式需要进行一定程度的限制。其限制的核心在于要对当前持有股票时候收益的递推公式进行限制:
(1)当只能进行一次股票购买的时候,在持有股票的状态下,之前是不可能发生任何持有股票的事件,因此上一天的dp[i - 1][0]只能和0 - prices[i] ( 0 收益减去当前股票价格 ) (0收益减去当前股票价格) (0收益减去当前股票价格)来进行比较。
(2)当不限制次数进行股票购买的时候,在持有股票前可能会存在收益,且收益为前一天不持有股票时候手里的资金。此时的更新就会与dp[i - 1][1] - prices[i]来进行与上一天持有的状态对比,几乎可以说每次进行max更新,都能看做一次新的持有次数更新(但并不准确,因为更新了不一定会被用于出售,而可能会被在下一次就被更低价的股票取代)。
所以,可以看出在上式子中,其实已经隐含了次数状态的转移,而该转移所体现的关键就是持有股票时收益状态的递推公式。故当指定进行两次股票购买后,我们可以显式的来对收益的天数进行限制,新规定出两个新的状态,来作为第二天的是否持有状态判定。同时,对两次的持有时收益方程来进行限制,第一次持有前的收益一定为0,第二次持有前的收益一定是第一次卖出时的收益。
即
d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , 0 − p r i c e s [ i ] ) ; dp[i][0] = max(dp[i - 1][0], 0 - prices[i]); dp[i][0]=max(dp[i−1][0],0−prices[i]);
d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] + p r i c e s [ i ] ) ; dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); dp[i][1]=max(dp[i−1][1],dp[i−1][0]+prices[i]);
d p [ i ] [ 2 ] = m a x ( d p [ i − 1 ] [ 2 ] , d p [ i − 1 ] [ 1 ] − p r i c e s [ i ] ) ; dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]); dp[i][2]=max(dp[i−1][2],dp[i−1][1]−prices[i]);
d p [ i ] [ 3 ] = m a x ( d p [ i − 1 ] [ 3 ] , d p [ i − 1 ] [ 2 ] + p r i c e s [ i ] ) ; dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]); dp[i][3]=max(dp[i−1][3],dp[i−1][2]+prices[i]);
因此,由以上推理,至少需要初始化四个状态才能完成上述状态转移。
代码如下:
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = 0 - prices[0];dp[0][1] = 0;dp[0][2] = 0 - prices[0];dp[0][3] = 0;for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], 0 - prices[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]);}return dp[prices.size() - 1][3];}
};
买卖股票的最佳时机IV
LeetCode题目:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
与问题三的分析相似,只不过将状态方程拓展到2*k即可,同时,为了方便循环的统一,可以在开始额外添加一个未进行任何股票操作的收益dp[0][0] = 0;以方便第一次股票持有收益初始化公式可以与其他次持有时候相同。
之后进行for循环进行初始化和迭代即可,最终代码如下:
class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));dp[0][0] = 0;for (int i = 1; i <= 2 * k; i++) {if (i % 2 == 1) {dp[0][i] = 0 - prices[0];}else {dp[0][i] = 0;} }for (int i = 1; i < prices.size(); i++) {for (int j = 0; j <= 2 * k; j++) {if (j == 0) {dp[i][j] = 0;}else if (j % 2 == 1) {dp[i][j] = max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);}else {dp[i][j] = max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);}}}return dp[prices.size() - 1][2 * k];}
};