代码随想录算法训练营
Day42 代码随想录算法训练营第 42 天 |LeetCode 188.买卖股票的最佳时机IV LeetCode309.最佳买卖股票时机含冷冻期 LeetCode714.买卖股票的最佳时机含手续费
目录
- 代码随想录算法训练营
- 前言
- 一、LeetCode 188.买卖股票的最佳时机IV
- 二、LeetCode309.最佳买卖股票时机含冷冻期
- 三、LeetCode714.买卖股票的最佳时机含手续费
- 股票问题总结
前言
LeetCode 188.买卖股票的最佳时机IV
LeetCode309.最佳买卖股票时机含冷冻期
LeetCode714.买卖股票的最佳时机含手续费
一、LeetCode 188.买卖股票的最佳时机IV
1.题目链接
2.思路
（1）dp[i][j] 表示当前最大现金
i: 第i天
j: 状态
0—从未持有股票
1—第一次持有股票
2—第一次卖出
…
2k-1 第k次持有股票
2k 第k次卖出股票
（2）状态转移
1）j是奇数 dp[i][p] = max(dp[i - 1][p], dp[i - 1][p - 1] - prices[i]);
2）j是偶数 dp[i][p] = max(dp[i - 1][p], dp[i - 1][p - 1] + prices[i]);
（3）初始化
1）j是奇数 dp[0][p] = -prices[0];
2）j是偶数 dp[0][p] = 0;
3.题解
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
int dp[n][2 * k + 2];
for (int p = 1; p < 2 * k + 2; p += 2) {
dp[0][p] = -prices[0];
dp[0][p - 1] = 0;
}
for (int i = 1; i < n; i++) {
dp[i][0] = 0;
for (int p = 1; p < 2 * k; p += 2) {
dp[i][p] = max(dp[i - 1][p], dp[i - 1][p - 1] - prices[i]);
dp[i][p + 1] = max(dp[i - 1][p + 1], dp[i - 1][p] + prices[i]);
}
}
return dp[n - 1][2 * k];
}
};
二、LeetCode309.最佳买卖股票时机含冷冻期
1.题目链接
2.思路
1）dp[i][j] 表示当前最大现金
i: 第i天
j: 状态
0—持有股票
1—未持有股票但是可以买入
2—未持有股票但是不可以买入
（2）状态转移
1）持有股票可以是前一天持有，也可以前一天未持有股票但是可以买入
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
2）前一天未持有股票但是可以买入，也可以前一天未持有股票但是不可以买入
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
3）前一天持有，今天卖出
dp[i][2] = dp[i - 1][0] + prices[i];
（3）初始化
持有股票：dp[0][0] = -prices[0];
从未持有： dp[0][1] = 0;
从未持有： dp[0][2] = 0;
3.题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][3];
// 0---持有 1---不持有且不在冷却期 2--冷却
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + prices[i]);
}
int ans = max(dp[n - 1][0], dp[n - 1][1]);
ans = max(ans, dp[n - 1][2]);
return ans;
}
};
三、LeetCode714.买卖股票的最佳时机含手续费
1.题目链接
2.思路
在买卖股票的最佳时机II 的基础上，每次出售时减去fee
3.题解
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n=prices.size();
int dp[n][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<n;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
}
return max(dp[n-1][0],dp[n-1][1]);
}
};
股票问题总结
- 121.买卖股票的最佳时机
dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得现金。
-
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0] 第i天买入股票，所得现金就是买入今天的股票后所得现金，因为此前不可能进行交易，所以从来没有持有过股票-prices[i] 所以dp[i][0] = max(dp[i - 1][0], -prices[i]); -
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1] 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
2.122.买卖股票的最佳时机II
（1）贪心算法：拆分利润，看成每天一买一卖，收集每天的正利润
（2）动态规划：
-
dp数组定义：
dp[i][0] 表示第i天持有股票所得现金 dp[i][1] 表示第i天不持有股票所得最多现金 -
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0] 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
- 188.买卖股票的最佳时机IV
最多买卖k笔交易，问最大收益
（1）dp[i][j] 表示当前最大现金
i: 第i天
j: 状态
0—从未持有股票
1—第一次持有股票
2—第一次卖出
…
2k-1 第k次持有股票
2k 第k次卖出股票
（2）状态转移
1）j是奇数 dp[i][p] = max(dp[i - 1][p], dp[i - 1][p - 1] - prices[i]);
2）j是偶数 dp[i][p] = max(dp[i - 1][p], dp[i - 1][p - 1] + prices[i]);
（3）初始化
1）j是奇数 dp[0][p] = -prices[0];
2）j是偶数 dp[0][p] = 0;
4.冷却期：
三个状态：
0—持有股票
1—未持有股票但是可以买入
2—未持有股票但是不可以买入