dp（八）买卖股票的最好时机 （一，二、三）
目录
买卖股票的最好时机(一)_牛客题霸_牛客网
买卖股票的最好时机(二)_牛客题霸_牛客网
买卖股票的最好时机(三)_牛客题霸_牛客网
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
【解法一】暴力枚举 贪心
通过从左侧找一个最小值，从最右侧找一个最大值，来进行买卖从而保存一个收益最大值
class Solution {
public:
int maxProfit(vector<int>& prices) {
// write code here
int n = prices.size();
vector<int> dp(n, 0);
dp[0] = 0;
int _max = 0;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
dp[i] = max(prices[i]-prices[j], dp[i]);
}
_max = _max>dp[i]?_max:dp[i];
}
return _max;
}
};【解法二】二维dp 动态规划
状态：确定俩个dp才存储股票持有与不持有情况
dp[i][0] 代表第i天时持有股票的最大值
dp[i][1]代表第i天不持有股票的最大值
状态转移：
对于持有股票来说分为第i天买这个股票和第i天不买这个股票俩种情况，不买股票那就延续上一天的情况，即F[i-1][0],买这个那就是花掉今天股票的钱，俩者选出一个最大值
dp[i][0] = max(dp[i-1][0], -prices[i]);
对于不持有股票来说分为第i天卖这个股票和第i天不卖这个股票，不卖这个股票那就是保持前一天不持有股票的状态，即F[i-1][1]，第i天卖这个股票就是在前一天持有股票的基础上得来prices
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
初始化
即为dp[0][0] 第一天持股 那就是买入第一天股票 -price[0]
即为dp[0][1] 第一天不持股那就是0
class Solution {
public:
int maxProfit(vector<int>& prices) {
// write code here
int n = prices.size();
vector<vector<int>> dp(n, vector<int> (2));
dp[0][0] = -prices[0]; // 持有股票时的最大值
dp[0][1] = 0; // 不持有股票的最大值
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i-1][0], -prices[i]);
dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1]);
}
return dp[n-1][1];
}
};买卖股票的最好时机(二)_牛客题霸_牛客网
你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
与上方的一几乎一致，不过问题就是这次可以进行多次的买和卖的操作。
状态：确定俩个dp才存储股票持有与不持有情况
dp[i][0] 代表第i天时持有股票的最大值
dp[i][1]代表第i天不持有股票的最大值
状态转移：
对于持有股票来说分为第i天买这个股票和第i天不买这个股票俩种情况，不买股票那就延续上一天的情况，即F[i-1][0]，这里的买股票就是要在前一天不持股的情况下进行购买了
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
对于不持有股票来说分为第i天卖这个股票和第i天不卖这个股票，不卖这个股票那就是保持前一天不持有股票的状态，即F[i-1][1]，第i天卖这个股票就是在前一天持有股票的基础上得来prices
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
初始化
即为dp[0][0] 第一天持股 那就是买入第一天股票 -price[0]
即为dp[0][1] 第一天不持股那就是0
class Solution {
public:
int maxProfit(vector<int>& prices) {
// write code here
int n = prices.size();
vector<vector<int>> dp(n, vector<int> (2));
dp[0][0] = -prices[0]; // 持有股票时的最大值
dp[0][1] = 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], dp[i-1][0]+prices[i]);
}
return max(dp[n-1][0] ,dp[n-1][1]);
}
};买卖股票的最好时机(三)_牛客题霸_牛客网
1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
// write code here
int n = prices.size();
vector<vector<int>> dp(n, vector<int> (5));
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
for(int i = 1; i < n; i++)
{
dp[i][1] = max(dp[i-1][1], -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[n-1][4];
}
};