力扣-股票买入问题
目录
力扣-股票买入问题
dp
dp元素代表最大利润
f[j][1]
代表第
j
次交易后持有股票的最大利润。在初始状态，持有股票意味着你花钱买入了股票，此时的利润应该是负数（扣除了买入股票的成本），而不是 0。所以，把
f[j][1]
初始化为负无穷大
f[j][0]
表示第
j
次交易完成后未持有股票的最大利润。当还未开始进行任何有效的股票买卖操作时，也就是处于初始状态，此时没有持有股票且利润为 0
所以有了如下初始化
for (int j = 0; j < k + 2; j++) {
for (int l = 0; l < 2; l++) {
f[j][l] = Double.NEGATIVE_INFINITY;
}
}
// 初始化状态，第 j 次交易未持有股票时利润为 0
for (int j = 1; j < k + 2; j++) {
f[j][0] = 0;
}
因为可以交易0~k次，一共k+1种选择，而i = 0时，状态转移会出现i=-1的dfs，所以要开辟k+2个空间，而我们实际填写k+1种
因为数组不能有-1的索引，所以整体偏移，用0代表-1，1代表0.所以j<0而不是j<=0
import java.util.List;
public class StockTrading {
public int maxProfit(List<Integer> prices) {
// 最多允许的交易次数
int k = 2;
// 初始化动态规划数组 f
double[][] f = new double[k + 2][2];
for (int j = 0; j < k + 2; j++) {
for (int l = 0; l < 2; l++) {
f[j][l] = Double.NEGATIVE_INFINITY;
}
}
// 初始化状态，第 j 次交易未持有股票时利润为 0
for (int j = 1; j < k + 2; j++) {
f[j][0] = 0;
}
// 遍历每一天的股票价格
for (int i = 0; i < prices.size(); i++) {
int p = prices.get(i);
// 从后往前更新状态
for (int j = k + 1; j > 0; j--) {
// 更新第 j 次交易未持有股票的最大利润
f[j][0] = Math.max(f[j][0], f[j][1] + p);
// 更新第 j 次交易持有股票的最大利润
f[j][1] = Math.max(f[j][1], f[j - 1][0] - p);
}
}
// 返回最终结果，即最后一次交易未持有股票的最大利润
return (int) f[f.length - 1][0];
}
}有冷冻期
修改状态转移方程
因为卖出的股票不能是前一天买入的了，所以不能-1要用合理时间的股票
交易次数必须为2
只需要不断维护两次交易的利润即可，不需要记录全部交易的利润
这里不用开辟k+2的空间了，因为规定必须交易两次，所以状态转移方程没有变量了，而是具体的1和2，就不会出现-1的情况
import java.util.List;
public class StockTrading {
public int maxProfit(List<Integer> prices) {
// 交易次数必须为2次
int k = 2;
// 初始化动态规划数组 f
// f[j][0] 表示第 j 次交易未持有股票的最大利润
// f[j][1] 表示第 j 次交易持有股票的最大利润
int[][] f = new int[k + 1][2];
// 初始化状态
for (int j = 1; j <= k; j++) {
f[j][0] = Integer.MIN_VALUE; // 初始时，未持有股票的利润为最小整数
f[j][1] = Integer.MIN_VALUE; // 初始时，持有股票的利润为最小整数
}
f[0][0] = 0; // 第0次交易未持有股票的利润为0
// 遍历每一天的股票价格
for (int i = 0; i < prices.size(); i++) {
int p = prices.get(i);
// 更新第 2 次交易的状态
f[2][0] = Math.max(f[2][0], f[2][1] + p); // 第 2 次交易未持有股票
f[2][1] = Math.max(f[2][1], f[1][0] - p); // 第 2 次交易持有股票
// 更新第 1 次交易的状态
f[1][0] = Math.max(f[1][0], f[1][1] + p); // 第 1 次交易未持有股票
f[1][1] = Math.max(f[1][1], -p); // 第 1 次交易持有股票
}
// 返回最终结果，即第 2 次交易未持有股票的最大利润
// 如果无法完成两次交易，返回 0 或其他特殊值
return Math.max(f[2][0], 0); // 确保不会返回负值
}
}网课：