leetcode 股票问题全序列

1 只允许一次交易，121题，买卖股票的最佳时机

class Solution {/*给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。*/
public:int maxProfit(vector<int>& prices) {if(prices.size()<2){return 0;}int maxP=0x80000000;int minPrice=prices[0];for(int i=1;i<prices.size();i++){if(minPrice>prices[i]){minPrice=prices[i];}maxP=max(maxP,prices[i]-minPrice);}return maxP;}
};

2 可以交易多次，122题， 买卖股票的最佳时机2

class Solution {/*题目：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
题解：
贪心
因为不限制交易次数，只要今天价格比昨天高，就交易，利润为正累加，最后的和就是最大的利润*/
public:int maxProfit(vector<int>& prices) {if(prices.size()<2){return 0;}int res=0;for(int i=0;i<prices.size()-1;i++){if(prices[i+1]>prices[i]){res+=(prices[i+1]-prices[i]);}}return res;}
};

3 最多2次交易，123题， 买卖股票的最佳时机3

class Solution {/*给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。题解：动态规划：dp[i][j] 中 i 表示第 i 天，j为 [0−4]五个状态，dp[i][j]表示第i天状态j所得最大现金j=0无操作 =1第一次买入，=2第一次卖出，=3第二次买入，=4第二次卖出|buy|buy|sell|sell|sell|buy|buy||---|---|----|----|----|---|---||    |当天第一次 保持卖出*/
public:int maxProfit(vector<int>& prices) {if(prices.size()<1){return 0;}// dp[i][j]表示第i天状态j所得最大现金vector<vector<int>>dp(prices.size(),vector<int>(5,0));// initdp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;//第一天就卖出 相当于第一次买入后又卖出了dp[0][3]=-prices[0];// 第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，// 然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少dp[0][4]=0;for(int i=1;i<prices.size();i++){// 1. 第i天无操作,则之前也是没有操作dp[i][0]=dp[i-1][0];// 2. 第i天第一次买入dp[i][1]=max(dp[i-1][1],//前一天买入，当天保持dp[i-1][0]-prices[i]//当天买入，前一天还是没有操作);// 3. 第i天第一次卖出dp[i][2]=max(dp[i-1][2],//前一天卖出，当天保持dp[i-1][1]+prices[i]//当天第一次卖出，前一天还是第一次买入);// 4. 第i天第二次买入dp[i][3]=max(dp[i-1][3],//前一天买入，当天保持dp[i-1][2]-prices[i]//当天买入，前一天还是第一次卖出);// 5. 第i天第二次卖出dp[i][4]=max(dp[i-1][4],//前一天卖出，当天保持dp[i-1][3]+prices[i]//当天第二次卖出，前一天还是第二次买入);}return dp[prices.size()-1][4];}
};

4. 最多k次交易，188题，买卖股票的最佳时间4

class Solution {/*题目：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。题解：定义一个三维数组dp[n][k][2]这里n表示天数，dp[i][j][0]：表示第i天交易了j次时卖出后的累计最大利润dp[i][j][1]：表示第i天交易了j次时买入后的累计最大利润1. 第一次买入：要么前一天买入后保持，要么从初始态第一次买入dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])第一次卖出（注意已经完成一次交易这里j=1）：要么前一天卖出后保持，要么从前一天第一次买入后，当天卖出dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])2. 第二次买入：要么前一天买入后保持，要么从前一天第一次卖出后当天第二次买入dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])第二次卖出（注意已经完成一次交易这里j=2）：要么前一天卖出后保持，要么从前一天第二次买入后，当天卖出dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])...j. 第j次买入：要么前一天买入后保持，要么从前一天第j-1次卖出后当天第二次买入dp[i][j-1][1]=max(dp[i-1][j-1][1],dp[i-1][j-1][0]-prices[i])第二次卖出（注意已经完成一次交易这里j=j）：要么前一天卖出后保持，要么从前一天第j次买入后，当天卖出dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])initfor(int i = 0; i <= k; ++i) {dp[0][i][0] = 0;// 第一天，不管交易多少次，卖出都是0收入dp[0][i][1] = -prices[0]; // 第一天，不管交易多少次，买入的收入是-prices[0]}三维数组太高了进行压缩，从上面DP公式可以知道，可以去掉天数纬度，用二维数组dp[k][2]来表示则有：dp[j-1][1]=max(dp[j-1][1],dp[j-1][0]-prices[i])dp[j][0]=max(dp[j][0],dp[j-1][1]+prices[i])*/
public:int maxProfit122(vector<int>&prices){// 不限制次数的交易if(prices.size()<2){return 0;}int res=0;for(int i=0;i<prices.size()-1;i++){if(prices[i+1]>prices[i]){res+=prices[i+1]-prices[i];}}return res;}int maxProfit(int k, vector<int>& prices) {int n=prices.size();if(k>=n){// 类似122题，不限制次数的交易return maxProfit122(prices);}// dp[j][z]交易第j次z=0时候卖出后的收益，// dp[j][z]交易第j次z=1时候买入后的收益vector<vector<int>>dp(k+1,vector<int>(2,0));// init 根据三维降级而得,第一天for(int i=0;i<k;i++){dp[i][0]=0;//第一天无论交易多少次，卖出后的收益都是0dp[i][1]=-prices[0];//第一天无论交易多少次，买入后的收益都是-price[0]}for(int i=1;i<prices.size();i++){for(int j=1;j<=k;j++){dp[j-1][1]=max(dp[j-1][1],dp[j-1][0]-prices[i]);dp[j][0]=max(dp[j][0],dp[j-1][1]+prices[i]);}}return dp[k][0];}
};