买卖股票问题
1.买卖股票, 是一类经典 dp 题; 整体的题面意思是 有 n 天的价格, 实现多次买卖, 使得利润最大
2.状态编码上其实就是几个维度
(i). 当天第几天
(ii). 当天结束是持有还是没持有, 也可以理解为当天买了 / 卖了 / 不动 这些动作
(iii). 当前交易次数是多少
(v). 引入交易手续费, 在卖出状态转移的时候会有一定影响
121.买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例 1：输入：[7,1,5,3,6,4] 输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
分析:
1.因为只选 1 次买入时间和 1 次 卖出时间, 且卖出时间必然在买入之后至少一天, 所以我们通过遍历卖出时间来找最大利润
2.我们遍历的是第 i 天作为卖出点的的最大利润, 因为买入点永远在卖出点之前, 遍历同步维护历史最低买入点
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) {
return 0;
}
int ans = INT_MIN;
// 维护第 i 天之前的历史最低点
int preMin = prices[0];
for (int i = 1; i < prices.size(); ++i) {
ans = max(ans, prices[i] - preMin);
preMin = min(preMin, prices[i]);
}
return (ans < 0) ? 0 : ans;
}
};
122.买卖股票的最佳时机II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润 。
示例 1：输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。
示例 2：输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。
示例 3：输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
分析:
1.对于第 i 天结束时的我们拿到的最大利润, 是和数组本身里面的元素的大小关系的分布有关的, 直觉上就是执行 [低买高卖] 这种策略遇到数组中相对较低的就买, 遇到相对较高的就卖, 但是这个相对高低关系是比较复杂的, 似乎不好找到统一的局部最优性的策略
2.因为最多持有1只股票, 每天的选择是有限的, 在持有的情况下, 只有卖和不卖 2 种操作, 在不持有的情况下, 我们只有买和不买两种操作; 我们遍历这种状态, 并按照利润最大的方向建立状态转移关系, 因此我们思考采用动态规划的方法, 但是状态应该如何定义呢? 有两个维度, 一个是现在第几天, 一个是当天结束的持有状态
3.状态分为两类, 我们用二维数组来编码一下: 一类是当天 (结束) 持有股票, 一类是当天 (结束) 未持有股票;
(i). dp[i][0] 表示第 i 天交易结束的时在 [没有持有股票] 的最大利润
(ii). dp[i][1] 表示第 i 天交易结束的时在 [持有股票] 的最大利润
dp[i][0] 表示第 i 天交易结束的时在 [没有持有股票] 的最大利润, 这种状态可能由两种可能的状态转移过来,
(i). 昨天也没有持有, 今天也没买; 这种情况下最大利润直接由昨天没有持有的状态可以转移过来;
(ii). 昨天有持有, 但是今天卖掉了; 这种情况下, 最大利润从昨天持有的状态下最大利润, 加上卖掉赚的利润也就是 prices[i]
因此得到状态转移
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] 表示第 i 天交易结束的时在 [持有股票] 的最大利润, 这种状态可能由两种可能的状态转移过来,
(i). 昨天有持有, 今天也没卖掉; 这种情况下最大利润就是前一天持有的最大利润转移过来
(ii). 昨天没持有, 今天买了; 这种情况下, 最大利润就是前一天持有的最大利润, 同时减去今天买下股票的付出 prices[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
4.边界条件, 需要确定初始的条件, 也就是第 0 天 (真实意义下的第 1 天) 的最大利润是什么?
dp[0][0] = 0, 第 0 天, 没有持有的时候, 利润为 0
dp[0][1] = -prices[0], 第 0 天结束买了股票的时候, 利润为-prices[0]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0] = 0;
dp[0][1] = -prices[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]);
}
return dp[n-1][0];
}
};
因为状态只有持有和不持有两种, 或者我们直接用两个独立数组维护持有或者未持有的状态, 不必拘泥于固定的 n 维数组
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<int> nohold(n);
vector<int> hold(n);
// 处理第 0 天
nohold[0] = 0;
hold[0] = -prices[0];
// 处理 1..n-1 天的状态转移
for (int i = 1; i < n; ++i){
hold[i] = max(hold[i-1], nohold[i-1] - prices[i]);
nohold[i] = max(nohold[i-1], hold[i-1] + prices[i]);
}
return nohold[n-1];
}
};
188.买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1：输入：k = 2, prices = [2,4,1] 输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：输入：k = 2, prices = [3,2,6,5,0,3] 输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
分析:
1.限制了交易次数的上限为 k 笔交易, 这里面 1 笔交易的定义是 [1 次买&& 1次卖] 算 1 笔交易, 相比 122, 我们在 1.时间天数状态 2.当天是否持有状态 基础上增加一个状态 3.恰好完成 j 笔交易的状态
2.状态怎么设置? 日子一天一天的状态转移, 每天把可能的成交笔数和状态转移加以描述; 用一系列变量存储 [持有状态], 用另一系列变量存储 [未持有状态]
3.hold[i][j] 表示到第 i 天恰好进行 j 笔交易, 并且持有股票的最大利润, 进行一笔交易表示多买入1次
4.noHold [i][j] 表示到第 i 天恰好进行 j 笔交易, 并且当天不持有股票的最大利润
// 当天持有 1.当天没买 2.当天买了
hold[i][j] = max(hold[i-1][j], noHold[i-1][j] - prices[i]);
// 当天未持有 1.昨天未持有, 今天没买 2. 昨天持有, 今天卖了
nohold[i][j] = max(noHold[i-1][j], hold[i-1][j] + prices[i]);
4.边界条件是什么? 这里不太好想, 我们细看一下怎么设置 第 0 天的状态;
hold[0][1] 第 0 天已持股, 交易次数1, 不合法状态, 设置一个最小值 INT_MIN/2
hold[0][2] 第 0 天已持股, 交易次数2, 不合法状态, 设置一个最小值 INT_MIN/2
hold[0][i] 第 0 天已持股, 交易次数i, 不合法状态, 设置一个最小值 INT_MIN/2
hold[0][0] 第 0 天已持股, 交易次数0, 只有唯一的合法情况是当天买了的状态, 最大利润为 -prices[0];
nohold[0][1] 第 0 天没持股, 交易次数1, 不合法状态, 设置一个最小值 INT_MIN/2
nohold[0][2] 第 0 天没持股, 交易次数2, 不合法状态, 设置一个最小值 INT_MIN/2
nohold[0][0] 第 0 天没持股, 交易次数0, 合法的状态, 利润是0
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> hold(n, vector<int>(k+1));
vector<vector<int>> nohold(n, vector<int>(k+1));
// 第 0 已经持股下的 0 笔交易, 只有一种可能是买了 prices[0], 最大利润 -prices[0]
hold[0][0] = -prices[0];
// 第 1 未持股下的 0 笔交易, 只有一种合法可能是什么都没做, 最大利润 0
nohold[0][0] = 0;
// 标记所有不合法的状态为一个较小的值, 比如 INT_MIN / 2
for (int i = 1; i <= k; ++i) {
hold[0][i] = INT_MIN / 2;
nohold[0][i] = INT_MIN / 2;
}
// 枚举天数
for (int i = 1; i < n; ++i) {
hold[i][0] = max(hold[i-1][0], nohold[i-1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
hold[i][j] = max(hold[i-1][j], nohold[i-1][j] - prices[i]);
nohold[i][j] = max(nohold[i-1][j], hold[i-1][j-1] + prices[i]);
}
}
return *max_element(nohold[n-1].begin(), nohold[n-1].end());
}
};
123.买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：输入：prices = [1,2,3,4,5] 输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：输入：prices = [1] 输出：0
分析:
1.更一般的分析详情见 188.买卖股票的最佳时机 IV
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int k = 2;
vector<vector<int>> hold(n, vector<int>(k+1));
vector<vector<int>> nohold(n, vector<int>(k+1));
// 第 0 已经持股下的 0 笔交易, 只有一种可能是买了 prices[0], 最大利润 -prices[0]
hold[0][0] = -prices[0];
// 第 1 未持股下的 0 笔交易, 只有一种合法可能是什么都没做, 最大利润 0
nohold[0][0] = 0;
// 标记所有不合法的状态为一个较小的值, 比如 INT_MIN / 2
for (int i = 1; i <= k; ++i) {
hold[0][i] = INT_MIN / 2;
nohold[0][i] = INT_MIN / 2;
}
// 枚举天数
for (int i = 1; i < n; ++i) {
hold[i][0] = max(hold[i-1][0], nohold[i-1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
hold[i][j] = max(hold[i-1][j], nohold[i-1][j] - prices[i]);
nohold[i][j] = max(nohold[i-1][j], hold[i-1][j-1] + prices[i]);
}
}
return *max_element(nohold[n-1].begin(), nohold[n-1].end());
}
};
309.最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1: 输入: prices = [1,2,3,0,2] 输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2: 输入: prices = [1] 输出: 0
分析:
1.状态分析, 相比没有冷冻期的情况, 冷冻期的出现只有出现持有股票的情况
2.我们用 dp[i][j] 来编码 第 i 天持有或者未持有且兼顾后一天是否冷冻的条件下的最大利润情况, 具体来说:
dp[i][0] 表示 i 天结束持有股票
dp[i][1] 表示 i 天结束没持有股票, 且之后一天是冷冻期
dp[i][2] 表示 i 天结束没持有股票, 且之后一天不是冷冻期
3.我们分类讨论一下所有可能的转移, 需要一点一点来看
// 当天结束持有股票的状态
dp[i][0] = max(
dp[i-1][0], // 昨天持有股票, 今天什么也没干的状态, 从昨天持有股票过来
dp[i-1][2] - prices[i]; // 昨天没持有股票, 今天买了的状态, 从昨天没有持有结束且后一天不是冷冻期 转移过来
)
// 当天结束没有持有股票, 且之后在冷冻期的, 就一种情况
dp[i][1] = max(
dp[i-1][0] + prides[i] // 昨天持有股票, 今天卖了, 之后冷冻期
)
// 当天结束没有持有股票, 且之后不在冷冻期
dp[i][2] = max(
dp[i-1][1] // 昨天没有持有股票, 今天是冷冻期
dp[i-1][2] // 昨天没有持有股票, 今天也不是冷冻期
)
4.边界条件
dp[0][0] 第 0 天持有股票, 合法情况是第 0 天买了 prices[0], 利润 -prices[0]
dp[0][1] 第 0 天未持有股票, 且后一天是冷冻期, 不合法, 利润 INT_MIN / 2;
dp[0][2] 第 0 天未持有股票, 且后一天不是冷冻期, 利润 0
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(3));
// dp[0][0] 第 0 天持有股票, 合法情况是第 0 天买了 prices[0], 利润 -prices[0]
// dp[0][1] 第 0 天未持有股票, 且后一天是冷冻期, 不合法, 利润 INT_MIN / 2;
// dp[0][2] 第 0 天未持有股票, 且后一天不是冷冻期, 利润 0
dp[0][0] = -prices[0];
dp[0][1] = INT_MIN / 2;
dp[0][2] = 0;
for (int i = 1; i < len; ++i) {
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = max(dp[i-1][1], dp[i-1][2]);
}
return max(dp[len-1][1], dp[len-1][2]);
}
};
714.买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 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示例 2：输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
分析:
1.将手续费算在最大利润的状态转移里面, 当且仅当卖出的时候才算手续费
nohold[i] = max(nohold[i-1], hold[i-1] + prices[i] - fee)
hold[i] = max(hold[i-1], nohold[i-1] - pricer[i])
2.边界条件
nohold[0] = 0 第 0 天没买入
hold[0] = -prices[0] 第 0 天买入
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
vector<int> nohold(len);
vector<int> hold(len);
nohold[0] = 0;
hold[0] = -prices[0];
for (int i = 1; i < len; ++i) {
nohold[i] = max(nohold[i-1], hold[i-1] + prices[i] - fee);
hold[i] = max(hold[i-1], nohold[i-1] - prices[i]);
}
return nohold[len-1];
}
};
转载请注明来源, from goldandrabbit.github.io
