Leetcode股票问题总结篇
- 动态规划的股票问题一共六道题，买卖股票最佳时机和买卖股票手续费都是一个类型的问题，维护好买入和卖出两个状态即可，方法一摸一样。而冷冻期也差不多就是状态多了点，买入、保持卖出、当日卖出、以及冷冻期四个状态。
- 做题方法还是动态规划五部曲：
- 明确dp数组含义，这里六道题全部第i天都是手里买入状态或者卖出状态的现金数是多少，这篇文章下标0代表未持有，下标1代表持有。
- 写出递推公式，下面写了最基本的，其他题的公式都是在这个基础上做了修改的：
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = max(dp[i - 1][1], -prices[i]);- 最佳时机2那道题就是在这个基础上，修改买入时的递推公式为
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i - 1]); - 最佳时机3那道题是增加两个状态表示第二次买入和卖出：
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]); dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]); - 最佳时机4那道题是增加到2 * k个状态，那么内层就要变为双层循环为各个状态赋值了。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]); - 冻结期那道题的递推公式就稍微复杂了，需要维护四个状态，分别是买入、保持卖出、当日卖出、以及冷冻期。
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]); dp[i][2] = dp[i - 1][0] + prices[i]; dp[i][3] = dp[i - 1][2]; - 含手续费这道题和第二道题一摸一样，在卖出时减去手续费就行。
- 最佳时机2那道题就是在这个基础上，修改买入时的递推公式为
- 初始化：每次买入的时候必须初始化为-price[0]，其他赋值为0即可。
- 遍历顺序：由于需要用到 i - 1的资金，所以从前往后遍历
121. 买卖股票的最佳时机
力扣题目链接
代码实现：
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size() + 1, vector(2, 0));
dp[1][0] = 0, dp[1][1] = -prices[0];//二维数组0代表不持有，1代表持有
for (int i = 2; i <= prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
dp[i][1] = max(dp[i - 1][1], -prices[i - 1]);
}
return dp[prices.size()][0];
}
- 动态规划二维数组滚动数组优化方式：
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(2, vector(2, 0));//只记录当前天和前一天的状态即可
dp[0][0] = 0, dp[0][1] = -prices[0];//二维数组0代表不持有，1代表持有
for (int i = 1; i < prices.size(); ++i) {
dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]);//看实现通过求余，每次取的都是前一个元素值
}
return dp[(prices.size() + 1) % 2][0];//用+1，因为数组可能为空
}
- 动态规划一维数组实现法，比二维实现更简洁
int maxProfit(vector<int>& prices) {
vector<int> dp(2, 0);//只记录当前天的状态即可
dp[0] = 0, dp[1] = -prices[0];//0代表不持有，1代表持有
for (int i = 1; i < prices.size(); ++i) {
dp[0] = max(dp[0], dp[1] + prices[i]);
dp[1] = max(dp[1], -prices[i]);
}
return dp[0];
}
- 贪心法实现（每次更新左边界为最小值，然后不断更新result结果）：
int maxProfit(vector<int>& prices) {
int low = INT_MAX, result = 0;
for (int i = 0; i < prices.size(); ++i) {
low = min(low, prices[i]);
result = max(result, prices[i] - low);
}
return result;
}
买卖股票的最佳时机2
力扣题目链接
思路：
- 在上题基础上增加了买卖次数，修改买入时的计算方法即可。
代码实现
- 普通动态规划想法，直接计算每天的利润（和贪心类似）
int maxProfit(vector<int>& prices) {
//dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
vector<int> dp(prices.size(), 0);
for (int i = 1; i < prices.size(); ++i) {
dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
}
return dp[prices.size() - 1];
}
- 用双状态实现的方法（这里用一维数组实现的，也可以是二维）
int maxProfit(vector<int>& prices) {
vector<int> dp(2, 0);
dp[0] = 0, dp[1] = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
dp[0] = max(dp[0], dp[1] + prices[i]);
dp[1] = max(dp[1], dp[0] - prices[i]);
}
return dp[0];
}
- 贪心法
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
profit += max(prices[i] - prices[i - 1], 0);
}
return profit;
}
- 双指针法
int maxProfit(vector<int>& prices) {
int profit = 0, buy_index = 0;
for (int i = 0; i < prices.size() - 1; i++) {
if (prices[i] > prices[i + 1]) {
profit += prices[i] - prices[buy_index];
buy_index = i + 1;
continue;
}
if (i + 1 == prices.size() - 1) {
profit += prices[i + 1] - prices[buy_index];
}
}
return profit;
}
买卖股票的最佳时机3
力扣题目链接
思路：
- 这道题规定只能买卖两次，实现方法上面已经写过了，直接上代码
代码实现
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][1] = -prices[0], dp[0][3] = -prices[0];//相当于当天买卖一次后再次买入
for (int i = 1; i < prices.size(); ++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]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.size() - 1][4];
}
买卖股票的最佳时机4
力扣题目链接
思路：
买卖次数规定为k次，需要利用循环给每次买卖赋值。
代码实现
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(k * 2 + 1, 0));
for (int i = 1; i < 2 * k + 1; i += 2) {
dp[0][i] = -prices[0];
}
for (int i = 1; i < prices.size(); ++i) {
for (int j = 1; j <= 2 * k - 1; j += 2) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
买卖股票的最佳时机含冷冻期
力扣题目链接
题目描述：
在第二题基础上，增加了冷冻期，需要维护四个状态
代码实现
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(4, 0));
dp[0][0] = -prices[0];
for (int i = 1; i < len; ++i) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(dp[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));
}
买卖股票的最佳时机含手续费
力扣题目链接
题目描述：
和第二题基本一样，卖出时减去手续费就行了
代码实现
int maxProfit(vector<int>& prices, int fee) {
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][1] = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.size() - 1][0];
}
