07股票交易问题
# 07 股票交易问题
股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。
| 题目 | 特点 |
|---|---|
| 121 买卖股票的最佳时机 (opens new window) | 只能买卖一次 |
| 122 买卖股票的最佳时机 II (opens new window) | 可以买卖多次 |
| 714 买卖股票的最佳时机含手续费 (opens new window) | 可以买卖多次，每次都有手续费 |
| 123 买卖股票的最佳时机 III (opens new window) | 最多买卖两次 |
| 188 买卖股票的最佳时机 IV (opens new window) | 最多买卖 k 次 |
| 309 最佳买卖股票时机含冷冻期 (opens new window) | 可以买卖多次，但是卖出有一天冷冻期 |
# 121 买卖股票的最佳时机 (opens new window)
给定一段时间内每天的股票价格，已知你只可以买卖各一次，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5
解析：
求最大利润本质是也是一个优化问题，所以可以采用动态规划的思路解决。
设置状态：用两个动态规划数组buy[i] 表示第 i 天持股时的现金数，sell[i]表示第 i 天不持股时的现金数
状态转移方程：第 i 天持股 buy[i] = max(buy[i-1],-prices[i])，如果第 i-1 天不持股则花费-prices[i]的现金买入股票，如果第i-1天持股，则保持不变；第 i 天不持股 sell[i] = max(sell[i-1],buy[i-1]+prices[i])，如果第 i-1 天也不持股那么情况不变，如果第 i-1 天持股则需要将其卖出产生收益buy[i-1]+prices[i]。
初始情况：第 1 天不持股sell[0] = 0；第 1 天持股buy[0] = -prices[0]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len<2) return 0;
vector<int> sell(len);
vector<int> buy(len);
sell[0] = 0;
buy[0] = -prices[0];
for(int i=1;i<len;++i){
buy[i] = max(buy[i-1],-prices[i]);
sell[i] = max(sell[i-1],buy[i-1]+prices[i]);
}
return sell[len-1];
}
}
本题也可以用更直接的方法解决，遍历一遍数组，在每一个位置 i 时，记录 i 位置之前所有价格中的最低价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益，一遍遍历完成后就可以得到最大收益。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sell = 0, buy = INT_MAX;
for(int i=0;i<prices.size();++i){
buy = min(buy,prices[i]);
sell = max(sell,prices[i]-buy);
}
return sell;
}
};
# 122 买卖股票的最佳时机 II (opens new window)
给定一段时间内每天的股票价格，已知你只可以多次买卖一支股票，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
解析：
本题和上一题的区别在于可以多次买卖，也可以采用动态规划的思路来解决。
设置状态：除了用两个数组分别表示股票持股与不持股情况，也可以使用一个二维数组dp[i][j]来表示，其中 i 表示交易的时间，j 表示交易状态即买入或卖出 ，0 表示买入状态、1表示卖出状态；dp[i][0]表示第 i 天持股时的现金数，dp[i][1] 表示第 i 天不持股时的现金数。值得注意的是dp[i][0]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，dp[i][1]亦同
状态转移方程：本题的状态转移方程和上一题的唯一区别在于第 i 天持股的情况，如果第 i-1 天也持股那么保持一致，如果第 i-1 天不持股由于可以进行多次交易，那么就需要在已获得收益的基础上花费-prices[i]的现金买入股票即dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i])。
初始情况：第 1 天持股dp[0][0] = -prices[0]，第 1 天不持股dp[0][1] = 0
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len<2) return 0;
vector<vector<int>> dp(len,vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1;i<len;++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[len-1][1];
}
};
本题可以采用贪心策略，由于不限制交易次数，只要今天股价比昨天高，就交易。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sum = 0;
for(int i=1;i<prices.size();++i){
if(prices[i]>prices[i-1]){
sum+=(prices[i]-prices[i-1]);
}
}
return sum;
}
};
# 714 买卖股票的最佳时机含手续费 (opens new window)
给定一段时间内每天的股票价格，已知每次交易都需要扣除fee的手续费，且每次只能拥有一支股票，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润 ((8 - 1) - 2) + ((9 - 4) - 2) = 8
解析：
本题本质上和122可多次交易并没有什么差别，主要的问题是需要考虑过多次数的交易可能会产生大量手续费，直接导致总的收益不如交易次数较少的利润。
设置状态：使用一个二维数组dp[i][j]来表示，其中 i 表示交易的时间，j 表示交易状态即买入或卖出 ，0 表示买入状态、1表示卖出状态；dp[i][0]表示第 i 天持股时的现金数，dp[i][1] 表示第 i 天不持股时的现金数。
状态转移方程：本题与122题状态转移方程的主要区别在于第 i 天不持股的情况，如果第 i-1 天也不持股那么保持一致，如果第 i-1 天持股，那么就需要将其卖出产生buy[i-1]+prices[i]的收益，同时需要从收益中扣除fee的手续费。得到第 i 天不持股情况的状态转移方程dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i] - fee)
初始情况：第 1 天持股dp[0][0] = -prices[0]，第 1 天不持股dp[0][1] = 0
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
if(len < 2) return 0;
vector<vector<int>> dp(len,vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1;i<len;++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] - fee);
}
return dp[len-1][1];
}
};
# 123 买卖股票的最佳时机 III (opens new window)
给定一段时间内每天的股票价格，已知你最多可以进行两次买卖一支股票，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
解析：
本题限制了交易次数最多为两次买卖，那么就要对这两次交易操作进行区分，所以一天的交易就不再是前两题中持股和不持股两种状态，而是要在此基础上区分第一次交易持股状态和第二次交易持股状态。
设置状态：使用一个二维数组dp[i][j]来表示，其中 i 表示交易的时间，j 为0～3表示交易状态。例如dp[i][0]表示第一次买入状态、dp[i][1]表示第一次卖出状态、dp[i][2]表示第二次买入状态、dp[i][3]表示第二次卖出状态。
状态转移方程：
- 第一次交易的状态转移方程与121的单次交易一致，如果第一次第 i 天持股
dp[i][0] = max(dp[i-1][0],- prices[i])，第 i-1 天不持股则需要花费-prices[i]的现金买入股票达成买入状态，如果第i-1天持股，则保持不变；- 如果第一次第 i 天不持股
dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i])，第 i-1 天也不持股那么情况不变，如果第 i-1 天持股则需要将其卖出达成卖出状态并产生收益prices[i]。- 第二次交易的状态转移方程则与122的多次交易大致相同，如果第二次交易第 i 天持股
dp[i][2] = max(dp[i-1][2],dp[i-1][1] - prices[i])，如果第 i-1 天也持股那么不进行操作，如果第 i-1 天不持股则需要在第一次交易完成的基础上花费prices[i]的现金买入股票达成持股或买入状态；- 如果第 i 天为卖不持股或卖出状态
dp[i][3] = max(dp[i-1][3],dp[i-1][2] + prices[i])，如果第 i-1 天不持股第 i-1 天也不持股那么情况不变，如果第 i-1 天持股则需要将其卖出达成卖出状态并产生收益prices[i]。
初始情况：第 1 天持股dp[0][0] = -prices[0], dp[0][1] = -prices[0]，第 1 天不持股dp[0][1] = 0, dp[0][3] = 0
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len<2) return 0;
vector<vector<int>> dp(len,vector<int>(4));
dp[0][0] = -prices[0];
dp[0][2] = -prices[0];
dp[0][1] = 0;
dp[0][3] = 0;
for(int i=1;i<len;++i){
dp[i][0] = max(dp[i-1][0],-prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
dp[i][2] = max(dp[i-1][2],dp[i-1][1]-prices[i]);
dp[i][3] = max(dp[i-1][3],dp[i-1][2]+prices[i]);
}
return dp[len-1][3];
}
};
# 188 买卖股票的最佳时机 IV (opens new window)
给定一段时间内每天的股票价格，已知你最多可以进行 k 次买卖一支股票，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
解析：
本题限制了交易次数最多为 k 次，那么就要根据 k 值大小区分不同情况，如果 k 大于数组长度那么就可以类比122题相当于可以不限次数交易；如果 k 小于数组长度那么就可以类比为123题有限次数交易求最大利润。
设置状态：还是使用一个二维数组dp[i][j]来记录所剩余的现金，其中 i 表示交易的时间，j 为表示交易状态。类比123题本题的不同在于交易次数是变化的，交易状态难以表征，但是我们也可以总结出规律，可以使用偶数表示买入状态，奇数表示卖出状态。
状态转移方程：本题的状态转移方程可以直接类比123题，区别在于次数是变化的。
初始情况：即所有交易次数中第一天不持股时为0，持股则为-prices[i]
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
// 临界情况 k <= 0 || k >= len
if(len < 2 || k <= 0) return 0;
if(len <= k){
return unlimitedTimes(prices);
}
// 一般情况 0 < k && k < len
vector<vector<int>> dp(len,vector<int>(2*k));
// 初始情况
for(int i=0;i<2*k;++i){
if(i&1){
dp[0][i] = 0;
}else{
dp[0][i] = -prices[0];
}
}
for(int i=1;i<len;++i){
// 第一次买入状态
dp[i][0] = max(dp[i-1][0],-prices[i]);
for(int j=1;j<2*k;++j){
if(j&1){
// 卖出状态转移方程
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
}else{
// 买入状态转移方程
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
}
}
}
return dp[len-1][2*k-1];
}
// 可以进行多次交易的贪心实现
int unlimitedTimes(vector<int>& prices){
int len = prices.size();
int sum = 0;
for(int i=1;i<len;++i){
if(prices[i]>prices[i-1]){
sum += (prices[i] - prices[i-1]);
}
}
return sum;
}
};
# 309 最佳买卖股票时机含冷冻期 (opens new window)
给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。
输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解析：
我们可以使用状态机来解决这类复杂的状态转移问题，通过建立多个状态以及它们的转移方式，我们可以很容易地推导出各个状态的转移方程。如图所示，我们可以建立四个状态来表示带有冷却的股票交易，以及它们的之间的转移方式。
其中分为买入状态Buy、卖出状态Sell、买入后状态S1和卖出后状态S2（状态的划分本人也没有搞清楚，仅仅凭个人理解进行划分，如有错误感谢指正）
- 买入状态：即通过买入股票达到的买入状态
- 买入后状态：买入大于等于两天后的持股状态，一直没操作，保持持股
- 卖出状态：通过卖出持有的股票达到卖出状态，可以从买入状态直接操作卖出股票进入卖出状态，也可以在买入之后的持有多天后卖出股票进入卖出状态，这两个过程都会产生收益
- 卖出后状态：度过了冷冻期，大于等于两天前就卖出了股票，一直没操作，保持不持股
设置状态：使用一个二维数组dp[i][j]来表示，其中 i 表示交易的时间，j 为0～3表示交易状态。例如dp[i][0]表示买入状态、dp[i][1]表示不操作状态、dp[i][2]表示卖出状态、dp[i][3]表示卖出后状态。
状态转移方程：
- 买入状态
dp[i][0] = dp[i-1][3] - prices[i]，卖出后状态下所持有的现金中花费prices[i]买入股票达到买入状态。- 买入后状态
dp[i][1] = max(dp[i-1][0],dp[i-1][1])，可以通过买入状态到达，也可以不操作，保持原先持股状态。- 卖出状态
dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + prices[i]，可以买入后第二天直接卖出股票到达卖出状态，也可以持有多天后再卖出股票达到卖出状态。- 卖出后状态
dp[i][3] = max(dp[i-1][2],dp[i-1][3])，可以通过卖出状态到达，也可以不操作，保持原先不持股状态。
初始情况：第一天不持股时为dp[0][2] = 0, dp[0][3] = 0，持股则为dp[0][0] = -prices[i], dp[0][1] = -prices[i]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len < 2) return 0;
vector<vector<int>> dp(len,vector<int>(4));
dp[0][0] = dp[0][1] = -prices[0];
dp[0][2] = dp[0][3] = 0;
for(int i=1;i<len;++i){
dp[i][0] = dp[i-1][3] - prices[i];
dp[i][1] = max(dp[i-1][0],dp[i-1][1]);
dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + prices[i];
dp[i][3] = max(dp[i-1][2],dp[i-1][3]);
}
return max(dp[len-1][2],dp[len-1][3]);
}
};