当前位置: 首页> 财经> 股票 > 青岛快速网站排名_东莞网站提升排名_知名seo公司_千度seo

青岛快速网站排名_东莞网站提升排名_知名seo公司_千度seo

时间:2025/7/11 10:57:00来源:https://blog.csdn.net/H2020fighting/article/details/145508866 浏览次数:0次
青岛快速网站排名_东莞网站提升排名_知名seo公司_千度seo

一、动态规划DP Ⅷ 买卖股票

1、买卖股票的最佳时机 121

这题之前贪心部分做过,找到前面股票的最低值,每次买卖股票都与之前的最低值进行交易,再找到利润最大的那次交易。

class Solution {
public:int maxProfit(vector<int>& prices) {int pre_min = INT_MAX, ans = 0;for(int price : prices){ans = max(ans, price - pre_min);pre_min = min(pre_min, price);}return ans;}
};

采用动态规划的思想来解决这题,每天有两个状态,持有股票和不持有股票,因此dp数组应该是二维的,dp[i][0]/dp[i][1]表示第i天持有/不持有股票时所拥有的最大利润。递推公式是,当天可以不买股票和买股票,持有股票的利润是在昨天持有股票的利润(今天不买)和今天买股票的开销中取最大值(因为只能买卖一次), d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , − p r i c e s [ i ] ) dp[i][0] = max(dp[i-1][0], -prices[i]) dp[i][0]=max(dp[i1][0],prices[i]);对于不持有股票,也有当天选择买和不买股票 d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] + p r i c e s [ i ] ) dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) dp[i][1]=max(dp[i1][1],dp[i1][0]+prices[i])

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][0]/[1]表示第i天持有/不持有股票得到利润vector<vector<int>> dp(n, vector<int>(2));dp[0][0] = -prices[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][1], dp[i-1][0] + prices[i]);}return dp[n-1][1];}
};

从递归公式发现当前值dp[i][0/1]只与前一天的dp值有关,我们可以进行空间复杂度的优化,只采用两个变量。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// buy/sale表示第i天持有/不持有股票得到利润int buy = -prices[0], sale = 0;for(int i=1; i<n; ++i){int tmp = buy;buy = max(buy, -prices[i]); // 只能买卖一次sale = max(sale, tmp + prices[i]);}return sale;}
};

2、买卖股票的最佳时机Ⅱ 122

这题在上一题的基础上去除掉了只能买卖一次的限制,贪心的做法是 只要股票涨了就卖,代码如下:

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;for(int i=1; i<prices.size(); ++i)ans += max(prices[i]-prices[i-1], 0);return ans;}
};

采用动态规划的思想解决,与上一道题类似,每天有两个状态,持有股票和不持有股票,dp数组的含义相同,不过由于此时不止可以买卖一次,所以dp方程需要进行修改, d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] − p r i c e s [ i ] ) dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]) dp[i][0]=max(dp[i1][0],dp[i1][1]prices[i]),dp[i][1]与上一题一样

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2));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][1], dp[i-1][0] + prices[i]);}return dp[n-1][1];}
};

空间复杂度优化:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// buy/sale表示第i天持有/不持有股票得到利润int buy = -prices[0], sale = 0;for(int i=1; i<n; ++i){int tmp = buy;buy = max(buy, sale-prices[i]); // 只能买卖一次sale = max(sale, tmp + prices[i]);}return sale;}
};

3、买卖股票的最佳时机Ⅲ 123

这题买卖次数限定为最多两次,对于每天就有买卖一/两 次持有/非持有股票的四个状态,他们之间的状态转移很容易分析。直接上代码:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][0/1/2/3] 分别表示第一次买卖后持有/非持有股票、第二次买卖后持有/非持有股票vector<vector<int>> dp(n, vector<int>(4));dp[0][0] = -prices[0];dp[0][2] = -prices[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][1], dp[i-1][0] + 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]);}return dp[n-1][3];}
};

空间复杂度优化代码如下,这个代码有个细节,在售卖的时候sell1 = max(sell1, buy1 + prices[i])使用的是当天的持有状态buy1而不是存储前一天buy1的临时变量。可以理解为今天买入股票又卖出股票,等于没有操作,保持昨天卖出股票的状态了。

class Solution {
public:int maxProfit(vector<int>& prices) {// 分别表示第一次买卖后持有/非持有股票、第二次买卖后持有/非持有股票int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;for(int i=1; i<prices.size(); ++i){buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]);}return sell2;}
};

二、写在后面

股票问题只要明确每天持有股票的状态,就比较好推导出状态转移关系。

关键字:青岛快速网站排名_东莞网站提升排名_知名seo公司_千度seo

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: