【Leetcode刷题记录】四种买卖股票问题

Archigenius / 2023-09-04 / 原文

前言：买卖股票问题大多数都是用动态规划解决，关键在于手上是否有股票，据此来找状态转移方程

1、买卖股票的最佳时机

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：买卖一次不需要动态规划，只需要建一个数组用来存放当前日期之后股票的最高价格，然后与当天的价格比较即可。

代码：C++

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int n = prices.size();
 5         vector<int> large(n);
 6         large[n-1] = prices[n-1];
 7         for(int i = n-2; i >= 0; --i){
 8             large[i] = max(large[i+1],prices[i+1]);
 9         }
10         int res{0};
11         for(int i = 0; i < n; ++i){
12             res = max(res,large[i] - prices[i]);
13         }
14         return res;
15     }
16 };

进阶：一次遍历。顺序遍历更新股票最小值，然后每次计算利润得到最大利润。

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int res{0};
 5         int minpri = prices[0];
 6         for(int i = 1; i < prices.size(); ++i){
 7             res = max(prices[i] - minpri,res);
 8             minpri = min(minpri,prices[i]);
 9         }
10         return res;
11     }
12 };

2、买卖股票的最佳时机II

题目：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

思路：不限制次数无脑动态规划。注意状态转移方程划分两种状态：1、手上不持有股票；2、手上持有股票。具体的状态转移方程看代码。

代码：C++

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int n = prices.size();
 5         vector<vector<int>> dp(n,vector<int>(2,0));
 6         dp[0][0] = -prices[0];
 7         for(int i = 1; i < n; ++i) {
 8             dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]);  //有股票在手
 9             dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i]);  //股票不在手/卖掉
10         } 
11         return dp[n-1][1];
12     }
13 }

进阶：贪心。一次遍历计算当天的股票与前一天的股票差，如果大于0，则加到结果里面

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int res{0};
 5         for(int i = 1; i < prices.size(); ++i){
 6             res += max(prices[i] - prices[i-1],0);
 7         }
 8         return res;
 9     }
10 };

3、买卖股票的最佳时机III

题目：给定一个数组，它的第i 个元素是一支给定的股票在第 i天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：动态规划！由于最多只能有两次交易，因此状态转移方程有四个，分别是第一次交易股票是否在手以及第二次交易股票是否在手，具体的状态转移方程看代码。

最后的答案可能是只需要一次交易就能得到最大利润，因此最终结果为第一次交易后和第二次交易后利润的最大值。

代码：C++

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int n = prices.size();
 5         vector<vector<int>> dp(n,vector<int>(4,0));
 6         dp[0][0] = -prices[0];
 7         dp[0][2] = -prices[0];
 8         for(int i = 1; i < n; ++i){
 9             dp[i][0] = max(dp[i-1][0],-prices[i]);              //第一支在手
10             dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i]);  //第一支卖掉
11             dp[i][2] = max(dp[i-1][2],dp[i-1][1] - prices[i]);  //第二支在手
12             dp[i][3] = max(dp[i-1][3],dp[i-1][2] + prices[i]);  //第二支卖掉
13         }
14         return max(dp[n-1][1],dp[n-1][3]);
15     }
16 };

4、买卖股票的最佳时机含冷冻期

题目：给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：动态规划！三种状态，分别是：有股票在手，股票卖出，冷冻期。具体状态转移方程看代码。

代码：C++

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int n = prices.size();
 5         vector<vector<int>> dp(n,vector<int>(3,0));
 6         dp[0][0] = -prices[0];
 7         for(int i = 1; i < n; ++i){
 8             dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i]);  //有股票在手
 9             dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i]);  //手上无股票
10             dp[i][2] = max(dp[i-1][2], dp[i-1][1]);             //冷静期
11         }
12         return max(dp[n-1][1],dp[n-1][2]);
13     }
14 };