前言：买卖股票问题大多数都是用动态规划解决，关键在于手上是否有股票，据此来找状态转移方程
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 };
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 };