309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费
309.最佳买卖股票时机含冷冻期
力扣题目链接(opens new window)
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
- 输入: [1,2,3,0,2]
- 输出: 3
- 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路
思路：动态规划 相比于买卖股票II，引入了冰冻期概念。需要将不持有股票的状态进行拆分。 分为三部分：刚卖出股票 正处于冰冻期 冰冻期结束 动态规划五部曲 1.dp数组以及下标代表含义 定义二维dp数组dp[i][j] 表示第i天最大利润 j = 0 表示持有股票 j = 1 表示刚卖出股票 j = 2 表示在冰冻期 j = 3 表示度过冰冻期 2.确定递推公式 第i天持有股票dp[i][0] 1.前一天持有股票 dp[i-1][0] 2.前一天在冰冻期 dp[i-1][2] - prices[i] 3.前一天度过冰冻期 dp[i-1][3] - prices[i] 第i天刚卖出股票 dp[i][1] 1.前一天持有股票 dp[i-1][0] + prices[i] 在冰冻期 dp[i][2] 1.前一天刚卖出股票 dp[i-1][1] 度过冰冻期dp[i][3] 1.前一天度过冰冻期 dp[i-1][3] 2.前一天在冰冻期 dp[i-1][2] 3.dp数组初始化 dp[0][1] = -prices[0] 4.遍历顺序，dp[i]由dp[i-1]推导，故正序 5.举例推导dp数组 时间复杂度o(n) 空间复杂度o(n)
代码如下
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int[][] dp = new int[prices.length][4];
dp[0][0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]), dp[i - 1][3] - prices[i]);
dp[i][1] = dp[i - 1][0] + prices[i];
dp[i][2] = dp[i - 1][1];
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2]);
}
return Math.max(Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]), dp[prices.length - 1][3]);
}
优化
二刷时使用另一种思路解决问题 相比上面的思路，我个人理解刚卖出股票这种状态，其实没有必要，也不好想。用持有股票的状态完全可以代替 而且上面的思路没有给出【没有买过股票的状态】（其实我们也可以不设置这个状态） 但我个人认为这种状态最好列出，会让状态流转更完整。 j = 0 未持有股票（包含两个状态1.没有买过股票和2.冷冻期度过后没有买股票） j = 1 持有股票 j = 2 处于冷冻期 未持有股票。1.前一天未持有股票2.前一天处于冷冻期 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]); 持有股票。1.前一天持有股票2.前一天未持有股票 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); 处于冷冻期。1.前一天刚卖出股票 dp[i][2] = dp[i - 1][1] + prices[i]; 时间复杂度o(n) 空间复杂度o(n)
代码如下
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int[][] dp = new int[prices.length][3];
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = dp[i - 1][1] + prices[i];
}
return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
}
714.买卖股票的最佳时机含手续费
力扣题目链接(opens new window)
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
- 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
- 输出: 8
解释: 能够达到的最大利润:
- 在此处买入 prices[0] = 1
- 在此处卖出 prices[3] = 8
- 在此处买入 prices[4] = 4
- 在此处卖出 prices[5] = 9
- 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:文章来源：https://www.toymoban.com/news/detail-794883.html
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
思路
思路：动态规划 跟买卖股票II相比，每次交易都有手续费。那么递推公式需要加上手续费用 动态规划五部曲 1.dp数组以及下标代表含义 定义二维dp数组dp[i][j] 表示第i天最大利润 j = 0 表示持有股票 j = 1 表示不持有股票 2.确定递推公式 手续费可以在买入股票时扣，也可在卖出股票扣。这里采用买入股票时扣手续费 第i天持有股票dp[i][0] 1.前一天持有股票 dp[i-1][0] 2.前一天未持有股票dp[i-1][1] - prices[i]-fee 第i天不持有股票 dp[i][1] 1.前一天持有股票 dp[i-1][0] + prices[i] 2.前一天未持有股票dp[i-1][1] 3.dp数组初始化 dp[0][1] = -prices[0] -fee 4.遍历顺序，dp[i]由dp[i-1]推导，故正序 5.举例推导dp数组 时间复杂度o(n) 空间复杂度o(n)
代码如下文章来源地址https://www.toymoban.com/news/detail-794883.html
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length == 0)
return 0;
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0] - fee;
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
}
return dp[prices.length-1][1];
}
到了这里，关于309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
