动态规划之买卖股票大集合
目录
引言
1.只能进行一次买卖股票（最多只能买一股股票）
2.可以进行多次股票买卖，且没有手续费（最多只能买一股股票）
3.可以进行多次股票买卖，但是有冷冻期，无手续费（最多只能买一股股票）
4.可以进行多次股票买卖，但是有手续费（最多只能买一股股票）
引言
作为动态规划中最常见的一类问题，买卖股票问题的思想也时常会出现在动态规划的题目中，买卖股票主要分为两大类，一种是有限制条件的，另一种是没有限制条件的
买卖股票问题主要的思路是用一个二维dp数组去存储是否持有股票的两个状态
比如说dp[ i ][ 0 ]表示就的就是在第i天持有股票的最大金额
dp[ i ][ 1 ]表示的就是在第i天没有持有股票的最大金额
然后我们就可以写出递推关系式
例如对于
（1）只能买一次股票来说
dp[i][0]=max(dp[i-1][0],-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]);
对于持有股票来说，由于只能购买一次，所以对于购买股票的时候，初始金额一定为0，因此我们的持有的状态只能由前一天持有的最小花费的状态和本天购买的花费的较小值推出来
不持有的状态是由前一天包括之前卖出股票的最大价值和在本天卖出股票的价值的较大者推出
（2）可以买卖多次股票
唯一的不同点在于购买的时候，因为可以买卖多次，因为购买股票的初始金额必然是有可能为非0的因此，我们要通过前一天包括之前不持有股票的状态推出今天持有股票的最大状态
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);//唯一不同点
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]);
当然了，这边的二维数组也可以将空间压缩成1维dp数组，让其变成一个滚动数组，从而降低空间复杂度
dp[ 0 ]指的就是持有股票的状态
dp[ 1 ]指的就是不持有股票的状态
1.只能进行一次买卖股票（最多只能买一股股票）
只能买卖一次 持有状态 不能由之前不持有的利润累加，就是持有状态永远都是0减去今天的价格
来看一道例题
传送门——买卖股票的最佳时机
题解：很标准的买卖股票问题，只能买卖一次，因此我们就可以用动规五部曲去完成这道题
1.明确dp数组的含义，首先就是dp[ i ][ 0 ]表示的是 对于第i天来说，持有股票的最大金额
dp[ i ][ 1 ]表示的是 对于第i天来说，不持有股票的最大金额
2.状态转移方程：dp[i][0]=max(dp[i-1][0],-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]);
3.初始化dp[1][0]=-p[1]//p[1]指的是第p天股票的价值,dp[1][1]=0;
4.遍历顺序，第一天遍历到第n天就行
二维dp数组：
#include<bits/stdc++.h>
using namespace std;int n;
int p[105];
int dp[105][2];
//dp数组的含义
//dp[i][0]表示的是在第i天拥有股票的最大价值，可以是在第i天买的股票，也可以是在之前买的
//说白了dp[i][0]统计的就是在第i天及之前，购进股票的最小花费
//dp[i][1]表示的是在第i天没有股票的最大价值，既可以是没有买，也可以是卖了又买了
//这个用于统计的就是买卖股票的最大价值
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];dp[1][0]=-p[1];//在第一天拥有股票的最大价值 dp[1][1]=0;//在第一天没有拥有股票的最大价值for(int i=2;i<=n;i++){dp[i][0]=max(dp[i-1][0],-p[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]);}cout<<dp[n][0]<<"\n";cout<<dp[n][1];return 0;
}一维dp数组：
//一维dp数组
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int dp[2];//dp[0]表示持有股票的状态，dp[1]指的是没持有股票的状态int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>p[i];}dp[0]=-p[1];dp[1]=0;for(int i=1;i<=n;i++){dp[0]=max(dp[0],-p[i]);dp[1]=max(dp[1],dp[0]+p[i]);}cout<<dp[1];return 0;} 2.可以进行多次股票买卖，且没有手续费（最多只能买一股股票）
传送门——买卖股票的最佳时机2
题解：也是很经典的股票买卖问题，并且是可以买卖多次，且不需要手续费的，唯一和·上面不同的就是去推不持有股票的状态发生了一些变化，其他的一样，包括dp数组的含义啊，遍历顺序啊，初始化啊，什么的，都是一样的
二维dp数组：
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int dp[105][2];int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];dp[1][0]=-p[1];dp[1][1]=0;for(int i=2;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);//唯一不同点//因为原来只能购买一次，所以计算最大的肯定是-p[i]，但是现在可以买卖多次，就说明初始值不一定为0，我们的初始值为dp[i-1][1]的值 dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]);}cout<<dp[n][1];return 0;
}一维的dp数组：
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int dp[2];//dp[0]持有股票，dp[1]不持有股票 int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];dp[0]=-p[1];dp[1]=0;for(int i=1;i<=n;i++){dp[1]=max(dp[1],dp[0]+p[i]);dp[0]=max(dp[0],dp[1]-p[i]);}cout<<dp[1];return 0;
}3.可以进行多次股票买卖，但是有冷冻期，无手续费（最多只能买一股股票）
这个相比于正常股票买卖问题在不持股状态分的更加细致，对于不持股状态可以分为，因为卖出的冷冻期导致不持股，或者是不是冷冻期导致的不持股，再算上持股状态，因此总共有三个状态，我们可以将其列举出来
0：持股状态
1：不是因为冷冻期而导致的不持股
2：因为冷冻期而导致的不持股
分别写出各自的状态转移方程
对于持股状态来说，他只能由之前的持股状态和不是冷冻期的不持股，买第i天的股票转移过来
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
对于不是因为冷冻期而导致的不持股来说，他只能由之前的非冷冻期不持股和冷冻期不持股推出来
（因为一旦卖出就要进入冷冻期，没办法由0推出1）
dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
对于因为冷冻期而导致的不持股来说，他只能由之前的持股状态卖出得到
dp[i][2]=dp[i-1][0]+p[i];
买卖股票的最佳时机含冷冻期
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int dp[105][3];
//0:持股状态
//1:不是因为卖出股票而导致的不持股
//2：因为卖出股票而导致的不持股 int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];dp[1][0]=-p[1];dp[1][1]=0;dp[1][2]=0;//第一天肯定不能是冷冻期，必然是0 for(int i=2;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][2]);dp[i][2]=dp[i-1][0]+p[i]; }cout<<max(dp[n][1],dp[n][2]);return 0;
}4.可以进行多次股票买卖，但是有手续费（最多只能买一股股票）
这个只需要在dp[1]的地方改一下即可，就是在获取到赚的钱的时候顺带减一下手续费就ok，难度比第三个低很多
买卖股票的最佳时机含手续费
题解：和第二个差不多，只不过多加了个手续费，状态转移方程变为dp[1]=max(dp[1],dp[0]+p[i]-fee);
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int dp[2];//dp[0]持有股票，dp[1]不持有股票 int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];int fee=0;cin>>fee;dp[0]=-p[1];dp[1]=0;for(int i=1;i<=n;i++){dp[1]=max(dp[1],dp[0]+p[i]-fee);dp[0]=max(dp[0],dp[1]-p[i]);}cout<<dp[1];return 0;
}