股票交易算法进阶：多笔交易与限制条件的动态规划解法
多笔股票交易的动态规划解法
问题描述：给定最大交易次数限制，计算股票交易的最大收益。这是对基础股票交易问题的扩展，需要考虑多笔交易的情况。
核心思路：我们为每一天维护2*k+1个状态，其中k是最大交易次数。状态交替表示买入和卖出操作。使用动态规划来跟踪每个状态下的最大收益。
状态转移方程：
- 买入状态（奇数索引）：保持之前状态或从前一状态买入
- 卖出状态（偶数索引）：保持之前状态或从买入状态卖出
优化实现：
class Solution {
public:
int maxProfit(int maxTransactions, vector<int>& stockPrices) {
if(stockPrices.empty()) return 0;
int days = stockPrices.size();
vector<int> buy(maxTransactions, -stockPrices[0]);
vector<int> sell(maxTransactions, 0);
for(int i = 1; i < days; ++i) {
for(int j = 0; j < maxTransactions; ++j) {
int prevBuy = (j == 0) ? -stockPrices[i] : sell[j-1] - stockPrices[i];
buy[j] = max(buy[j], prevBuy);
sell[j] = max(sell[j], buy[j] + stockPrices[i]);
}
}
return sell[maxTransactions-1];
}
};
含冷冻期的股票交易策略
问题描述：在卖出股票后需要有一天的冷冻期，期间不能买入股票。计算在这种限制下的最大收益。
状态分析：每天可能有三种状态：
- 持有股票（可以买入或保持）
- 刚刚卖出股票（进入冷冻期）
- 冷冻期或未持股状态（可以买入）
动态规划实现：
class Solution {
public:
int maxProfit(vector<int>& stockValues) {
int n = stockValues.size();
if(n < 2) return 0;
vector<int> hold(n, 0), sold(n, 0), rest(n, 0);
hold[0] = -stockValues[0];
sold[0] = INT_MIN;
rest[0] = 0;
for(int i = 1; i < n; ++i) {
hold[i] = max(hold[i-1], rest[i-1] - stockValues[i]);
sold[i] = hold[i-1] + stockValues[i];
rest[i] = max(rest[i-1], sold[i-1]);
}
return max(sold[n-1], rest[n-1]);
}
};
考虑交易手续费的股票买卖
问题描述：每次卖出股票时需要支付固定手续费，计算最大收益。
解题思路：这个问题与无限制交易类似，只需在卖出时扣除手续费。我们维护两个状态：持股收益和不持股收益。
空间优化解法：
class Solution {
public:
int maxProfit(vector<int>& marketPrices, int transactionCost) {
if(marketPrices.empty()) return 0;
int holding = -marketPrices[0];
int cash = 0;
for(int i = 1; i < marketPrices.size(); ++i) {
int newHolding = max(holding, cash - marketPrices[i]);
int newCash = max(cash, holding + marketPrices[i] - transactionCost);
holding = newHolding;
cash = newCash;
}
return cash;
}
};
以上三种问题都是股票交易系列的经典变体，通过动态规划可以有效地找到最优解。关键在于正确定义状态和状态转移方程，并根据具体约束条件进行相应的调整。
