day53|● 123.买卖股票的最佳时机iii ● 188.买卖股票的最佳时机iv-爱代码爱编程
123. 买卖股票的最佳时机 III
1.代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>>f(len, vector<int>(5, 0));
f[0][1] = -prices[0];f[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
f[i][0] = f[i - 1][0];
f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i]);
f[i][3] = max(f[i - 1][3], f[i - 1][2] - prices[i]);
f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i]);
}
return f[len - 1][4];
}
};
2.递归五部曲
题意:昨天写的是买卖股票1次和人一次,这里是买卖股票两次
1.确定dp数组和dp数组的含义
dp[i][0] 代表不买股票得到的最大利润
dp[i][1] 代表持有第一张股票的利润
dp[i][2] 代表不持有第一张股票(已经卖出)的最大利润
dp[i][3] 代表持有第二张股票的最大利润
dp[i][4] 代表不持有第二张股票的最大利润
2.确定递推公式
递推公式一般由前面的已知状态(已知dp元素)推导而来,这也是动态规划的精髓
一,dp[i][0]肯定只能由上一个的dp[i - 1][0]]推导而来,因为只有一种情况,还没有进行操作
二.dp[i][1]可以由上一个不持有股票,今天刚好买进股票,状态表达为f[i - 1][0] - prices[0],也可能上一个就持有了股票,就继承了这个状态dp[i - 1][1]
三dp[i][2]可以由上一个状态继承,也有可能是上一个状态持有这个股票,今天卖出,f[i - 1][1] + prices[0]
四.dp[i][3]也能共够由上一个状态继承,和今天刚好买股票
五:自行推导
f[i][0] = f[i - 1][0];
f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i]);
f[i][3] = max(f[i - 1][3], f[i - 1][2] - prices[i]);
f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i]);
3.初始化dp数组
由推导公式可知需要前面一天的全部状态,买进股票都是-prices[0]利润
4.确定遍历顺序
由左向右遍历,直到遍历到最后一天
5.模拟
188. 买卖股票的最佳时机 IV
1.代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
vector<vector<int>>f(len, vector<int>(2 * k + 1, 0));
for (int i = 1; i <= 2 * k; i += 2) {
f[0][i] = -prices[0];
}
for (int i = 1; i < len; i++) {
for (int j = 0; j <= 2 * k - 2; j += 2) {
f[i][j + 1] = max(f[i - 1][j + 1], f[i - 1][j] - prices[i]);
f[i][j + 2] = max(f[i - 1][j + 2], f[i - 1][j + 1] + prices[i]);
}
}
return f[len - 1][2 * k];
}
};
2.递归五部曲
题意:需要进行k次购买股票,说明在III的基础上需要寻找规律
1.确定dp数组和其下标
这里有多少个状态,根据上一题推导有2*k + 1个状态,意义和上面一样
2.推导公式
根据上一可以得出规律,需要分成两个dp状态为一组,因为后面的prices[i]的符号不一样,可以避免了很多麻烦,
dp[i][0] 可以不写因为不操作相当于0
dp[i][j + 1]可以有上一个状态继承dp[i - 1][j + 1],也能够在今天买这支股票,最大利润为dp[i - 1][j] - prices[i]
dp[i][j + 2] 代表不持有当前的股票,可能是继承上一个状态f[i - 1][j + 2],也可能是今天卖出股票f[i - 1][j + 1] + prices[i]
3.初始化
由规律可知,买入股票的时候都是-prices[0]
4.确定遍历顺序
由左到右遍历每一天,因为这里的状态太多,需要用for循环遍历这些状态,进行今天的状态推导
5.模拟