188.买卖股票的最佳时机IV
题目链接：188.买卖股票的最佳时机IV
文档讲解：代码随想录
状态：不会
思路：
在股票买卖1使用一维dp的基础上，升级成二维的即可。
- 定义dp[k+1][2]，其中 dp[j][0] 表示第j次交易后持有股票的最大利润，dp[j][1] 表示第j次交易后不持有股票的最大利润。
- 初始化时，对所有持有股票的情况要变成dp[i][0] = -prices[0];
题解：
要注意： dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票
public int maxProfit(int k, int[] prices) {
// 特殊情况处理，如果价格数组为空或只有一个元素，返回0
if (prices.length == 0) return 0;
// dp数组定义为k+1行，2列
// dp[j][0] 表示第j次交易后持有股票的最大利润
// dp[j][1] 表示第j次交易后不持有股票的最大利润
int[][] dp = new int[k + 1][2];
// 初始化第1到第k次交易后的持有股票的最大利润为 -prices[0]
for (int i = 1; i <= k; i++) {
dp[i][0] = -prices[0];
}
// 遍历每一天的股票价格
for (int i = 1; i < prices.length; i++) {
// 倒序遍历每一次交易,也可以正序,但是倒序更快一点
for (int j = k; j >= 1; j--) {
// 更新第j次交易后不持有股票的最大利润
dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);
// 更新第j次交易后持有股票的最大利润
// dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票
dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
}
}
// 返回最多k次交易后不持有股票的最大利润
return dp[k][1];
}
309.最佳买卖股票时机含冷冻期
题目链接：309.最佳买卖股票时机含冷冻期
文档讲解：代码随想录
状态：不会
思路：
第i天的最大收益由持有和不持有股票两种状态推导出来，考虑到由冷冻期，那么第i天持有股票可以考虑跳过昨天，从前天推导。
假设有今天持股情况下的最大收益 dp[i][0]、昨天不持股的最大收益 dp[i−1][0]、昨天持股的最大收益 dp[i−1][0]、前天不持股的最大收益 dp[i−2][1]，前天持股的最大收益 dp[i−2][0]。先将目光集中在前天，分别考虑前天持股与不持股的情况，试试能不能推导出今天的最大收益。
对于 dp[i−2][0] 来说，它表示前天结束时手中还有股票，那么如果昨天选择将前天的股票卖掉，由于冷冻期的存在，今天是不能交易的，自然今天手中也不可能还有股票，推导不出 dp[i][0]，因此这种情况可以直接忽略；如果前天选择保留股票到昨天，昨天也只能继续保留股票才能让今天手中也有股票，这时 dp[i][0]=dp[i−1][0]，这种情况已经在上面的状态转移方程中考虑到了，因此也不用担心。
对于 dp[i−2][1] 来说，它表示前天结束时手中没有股票，如果昨天买入股票，只能是将股票保留到今天才能推出 dp[i][0]，这时 dp[i]=dp[i−1][0] 在状态转移方程中已经考虑到了；如果昨天不买入股票，那么由于昨天手中没有股票，只能是今天买入，同时因为昨天没交易，昨天的最大收益和前天相同 dp[i−1][1]=dp[i−2][1]，所以这种情况的最大收益是 dp[i−2][1]−prices[i]。
题解：
public int maxProfit(int[] prices) {
int n = prices.length;
// 如果价格数组长度为0，直接返回0
if (n == 0) {
return 0;
}
// 定义一个二维数组 dp，dp[i][0] 表示第 i 天持有股票的最大利润，
// dp[i][1] 表示第 i 天不持有股票的最大利润
int[][] dp = new int[n + 1][2];
// 初始化第一天的状态
dp[1][0] = -prices[0]; // 第一天持有股票，利润为负的当前股票价格
// 从第二天开始遍历价格数组
for (int i = 2; i <= n; i++) {
// 第 i 天持有股票的最大利润，可以选择前一天也持有股票，或者前两天不持有股票，今天买入
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);
// 第 i 天不持有股票的最大利润，可以选择前一天也不持有股票，或者前一天持有股票，今天卖出
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);
}
// 返回倒数第二天不持有股票的最大利润
return dp[n][1]; // 因为是倒数第二天，所以这里改为 dp[n][1]
}
714.买卖股票的最佳时机含手续费
题目链接：714.买卖股票的最佳时机含手续费
文档讲解：代码随想录
状态：终于做出来一道了。。。。
思路：和股票买卖第2道题一样，不过每次卖出的时候扣除手续费就好了。
题解：
public int maxProfit(int[] prices, int fee) {
if (prices.length == 1) {
return 0;
}
int hasStock = -prices[0]; // 第一天买入股票后的收益
int noStock = 0; // 第一天不买股票的收益
for (int i = 1; i < prices.length; i++) {
// 今天选择买入股票或者保持昨天持有股票的状态
hasStock = Math.max(hasStock, noStock - prices[i]);
// 今天选择卖出股票或者保持昨天没有股票的状态
noStock = Math.max(noStock, hasStock + prices[i] - fee);
}
return noStock; // 最后一天不持有股票的最大收益
}
