一，买卖股票的最佳时机
【题目描述】
有一个价格数组prices，表示第i天的股票价格为prices[i]，整个过程只能买入股票和卖出股票一次。并且买入股票必须再卖出股票之前。
【思路】
贪心
我们可以遍历一次数组，遍历到prices[i]，表示在第i天卖出股票，为了使利益最大，我们需要在前i-1天中选择股票价格最低的一天买入。可以使用一个变量leftMin来记录前i-1天中，股票最低的价格。那么此时的最大利益就是prices[i]-leftMin。
#include <iostream>
using namespace std;
const int N=1e5+10;
int prices[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>prices[i];
//记录前i-1天中股票最低的价格
int leftMin=0x3f3f3f3f;
int ans=0;
for(int i=1;i<n;i++)
{
leftMin=min(leftMin,prices[i-1]);
ans=max(ans,prices[i]-leftMin);
}
cout<<ans<<endl;
return 0;
}动态规划
dp[n][2]：dp[i][0]表示第i天未持有股票的最大利益，dp[i][1]表示第i天持有股票的最大利益。
状态转移方程：
dp[i][0]两种情况：1，前一天仍未购买 2，之前购买，现在卖出
dp[i][0]=max(dp[i-1][0]，dp[i-1][1]+prices[i]）
dp[i][1]两种情况：1，之前买了，现在也不卖 2，之前没买，现在卖了
dp[i][1]=max(dp[i-1][1],-prices[i]）
初始值dp[0][0]=0。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int prices[N];
int dp[N][2];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>prices[i];
//记录前i-1天中股票最低的价格
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],-prices[i]);
}
cout<<dp[n-1][0];
return 0;
}二，买卖股票的最佳时机2
【问题描述】
本题与上题相似，区别是本题可以进行多次买卖。
【思路】
贪心
对于股票数组prices，根据prices[i]的大小，prices数组可能由以下几个部分组成：
某个区间prices[i]呈现上升趋势，某个区间prices[i]呈现下降趋势，某个区间prices[i]呈现上升趋势。
而为了求出最大利益，我们只需每个上升的区间，只需在开始买入，结束卖出即可。
#include <iostream>
using namespace std;
const int N=1e5+10;
int n;
int arr[N];
int main()
{
cin>>n;
int ret=0;
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=1;i<n;i++)
if(arr[i]>arr[i-1])
ret+=arr[i]-arr[i-1];
cout<<ret<<endl;
return 0;
}动态规划
同理 ，dp[n][2]。
dp[i][0]：表示第i天不持有股票的最大利益。
dp[i][1]：表示第i天持有股票的最大利益。
分析：
dp[i][0]：第i天不持有股票，那么该状态可以来自两方面。1，dp[i-1][0]，前一天不持有股票，今天也不持有，最大利益不变；2，dp[i-1][1]+prices[i]前一天持有股票，今天将股票卖出。所以，可得：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])。
dp[i][1]：第i天持有股票。前一天持有股票，今天继续 持有，也就是dp[i-1][1]；前一天不持有股票，几天持有股票（买入股票），也就是dp[i-1][0]-prices[i]。所以，可得：dp[i][0]=max(dp[i-1][1],dp[i-1][0]-prices[i])。
#include <iostream>
using namespace std;
const int N=1e5+10;
int n;
int dp[N][2];
int prices[N];
int main()
{
cin>>n;
int ret=0;
for(int i=1;i<=n;i++)
cin>>prices[i];
dp[1][1]=-prices[1];
dp[1][0]=0;
for(int i=2;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]);
}
cout<<dp[n][0]<<endl;
return 0;
}三，买卖股票的最佳时机3
【问题描述】
本题中，我们最多只能完成2笔交易。并且第一笔交易完成后才能进行第二笔交易。
【思路】
动态规划
首先看几个例子：
prices = [3,3,5,0,0,3,1,4]，对于这种情况，我们需要交易两次，可以获得的最大利益是6。
prices = [1,2,3,4,5]，对于这种情况，最大利益是在第一天买入，在最后一天卖出。只交易一次。
prices = [7,6,4,3,1] ，对于这种情况，最大利益是0，我们不进行交易，交易次数为0。
所以最大利益可能是在交易2次，交易1次或者交易0次的情况下。
首先定义状态表示：dp[i]表示，第i天结束时，最大的利益。
但是对于第i天，有多种状态，比如第i天处于买入状态，或者第i天处于卖出状态。还有第i天的时候，交易了多少次。所以我们使用这种一维的dp是无法表示的。
更改后的状态表示：
注意：买入状态表示我们手里有股票，卖出状态表示手里没有股票，处于可交易的状态。
f[i][j]：表示第i天结束后，处于买入状态，交易次数为j，此时的最大利益。
g[i][j]：表示第i天结束后，处于卖出状态，交易次数为j，此时的最大利益。
状态转移方程的分析：
f[i][j]：表示第i天处于买入状态，状态可以来自两方面：1，前一天处于买入状态，今天仍处于买入状态，即f[i-1][j]。2，前一天处于卖出状态，今天买入股票，处于买入状态，即g[i-1][j]-prices[i]。
所以f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])。
g[i][j]：表示第i天处于卖出状态，状态可以来自两方面：1，前一天处于卖出状态，今天仍处于卖出 状态，即 g[i-1][j]。2，前一天处于买入状态，今天卖出股票，处于卖出状态。此时就是完成一笔交易。即f[i-1][j-1]+prices[i]。注意这里交易次数的变化，前一天的交易次数为j-1，今天卖出股票后，交易次数++，交易次数变为j。
所以g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i])。j-1可能会出现负数，需要判断。
f表和g表的初始化问题：
f[0][0]=-prices[0]，第一天买入状态，交易0次，最大利益为-prices[0]。
g[0][0]=0，第一天手里没有股票，交易0次，处于卖出状态，最大利益为0。
根据状态表示的定义：f[0][j]，j从1开始，表示交易j次。但是第一天无法交易j次，所以这些位置 是没有意义的，为了不影响计算，可以初始化为无穷小。
同理，g[0][j]，j从1开始，表示交易j次。但是第一天无法交易j次，所以这些位置也没有意义，为了不影响计算，可以初始化为无穷小。
但是对于g表的状态计算时，有减法的操作，可能会超出范围。
所以可以 将 无穷小用-0x3f3f3f3f替换，这个数为无穷小的一半。
综上 ，开始时，可以将f表和g表全部初始化为-0x3f3f3f3f，f[0][0]和g[0][0]修改，其余部分在填表时做修改。
【代码】
//股票问题3
const int N = 1e5 + 10;
const int INF = -0x3f3f3f3f;
int n;
int prices[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> prices[i];
//j=3,交易次数为0，1，2
vector<vector<int>> f(n, vector<int>(3, INF));
auto g = f;
//初始化
f[0][0] = -prices[0];
g[0][0] = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if (j - 1 >= 0)
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
//交易0次，1次，2次的最大利益
int ans = 0;
for (int j = 0; j < 3; j++)
ans = max(ans, g[n - 1][j]);
cout << ans << endl;
return 0;
}四，买卖股票的最佳时机4
本题思路与买卖股票3的思路完全一致，只是交易次数的变化，分析思路一摸一样。只需将数组中j的大小由3改为k+1即可。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
const int INF = -0x3f3f3f3f;
int n,k;
int prices[N];
int main()
{
cin >> n>>k;
for (int i = 0; i < n; i++)
cin >> prices[i];
//j=k+1,交易次数为0，1，2......k
vector<vector<int>> f(n, vector<int>(k+1, INF));
auto g = f;
//初始化
f[0][0] = -prices[0];
g[0][0] = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < k+1; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if (j - 1 >= 0)
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
//交易0次，1次，2次的最大利益
int ans = 0;
for (int j = 0; j < k+1; j++)
ans = max(ans, g[n - 1][j]);
cout << ans << endl;
return 0;
}五，买卖股票的最佳时机含冷冻期
【问题描述】
本题包含冷冻期，在卖出股票后的一天，进入冷冻状态，无法买入股票。
【思路】
动态规划（状态机问题）
首先定义状态表示：dp[i]表示第i天结束后，获得的最大利益。
但对于第i天，存在多种状态：买入状态，卖出状态，冷冻期。
所以需要重新定义状态表示：
dp[i][0]：表示第i天之后，处于买入状态，此时的最大利益。
dp[i][1]：表示第i天之后，处于卖出状态，此时的最大利益。
dp[i][2]：表示第i天之后，处于冷冻期状态，此时的最大利益。
状态转移方程分析：
dp[i][0]：第i天结束后处于买入状态。可以从两方面转移得到：1，前一天处于买入状态，今天仍处于买入状态，即dp[i-1][0]。2，前一天处于卖出状态，今天买入股票后，处于买入状态，即dp[i-1][1]-prices[i]。
所以可得：dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])。
dp[i][1]：第i天结束后处于卖出状态。可以从两方面转移得到：1，前一天处于卖出状态，今天人处于卖出状态，即dp[i-1][1]。2，前一天处于处于冷冻期，今天就处于卖出状态，即dp[i-1][2]
所以可得：dp[i][1]=max(dp[i-1][1],dp[i-1][2])。
dp[i][2]：第i天结束之后处于冷冻期，只有一种情况：前一天处于买入状态，今天将股票卖出即可。dp[i-1][0]+prices[i]。
所以dp[i][2]=dp[i-1][0]+prices[0]。
初始化问题
dp[0][0]表示第一天处于买入状态，所以dp[0][0]=-prices[0]。
dp[0][1]表示第一天处于卖出状态，所以dp[0][1]=0。
dp[0][2]表示第一天处于 冷冻期，那我们可以将第一天的股票买了又卖掉，利益还是0,dp[0][2]=0。
返回值
只需求出最后一天处于卖出状态和冷冻期状态下的最大值即可。
【代码】
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<vector<int>> dp(n,vector<int>(3));
dp[0][0]=-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][2],dp[i-1][1]);
dp[i][2]=dp[i-1][0]+prices[i];
}
return max(dp[n-1][1],dp[n-1][2]);
}
};六，买卖股票的最佳时机含手续费
【问题描述】
在完成一次交易后（买入一次卖出一次），需要支付一次手续费，求最大利益。
支付手续费的时候，可以选择在买入的时候支付或者是在卖出的时候支付。
【思路】
状态定义：
f[i]：表示第i天结束之后，处于买入状态，此时的最大利益。
g[i]：表示第i天结束之后，处于卖出状态，此时的最大利益。
状态转移方程：
f[i]：第i天结束之后处于买入状态。1，前一天处于买入状态，今天仍然处于买入状态，即f[i-1]。
2，前一天处于卖出状态，今天买入股票即可。即g[i-1]-prices[i]。
所以f[i]=max(f[i-1],g[i-1]-prices[i])。
g[i]：第i天结束之后处于卖出状态。1，前一天处于卖出状态，今天仍处于卖出状态，即g[i-1]。
2，前一天处于买入状态，今天卖出股票即可，同时支付手续费。即f[i-1]+prices[i]-fee。
所以g[i]=max(g[i-1],f[i-1]+prices[i]-fee)。
返回值
g[n-1]，表示最后一天把股票卖出去的最大利益。f[n-1]表示最后一天还持有一张股票的最大利益。
g[n-1]一定比f[i-1]大，多以返回g[n-1]即可。
【代码】
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n=prices.size();
vector<int> f(n);
auto g=f;
f[0]=-prices[0],g[0]=0;
for(int i=1;i<n;i++)
{
f[i]=max(f[i-1],g[i-1]-prices[i]);
g[i]=max(g[i-1],f[i-1]+prices[i]-fee);
}
return g[n-1];
}
};