一、动态规划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[i−1][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[i−1][1],dp[i−1][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[i−1][0],dp[i−1][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;}
};
二、写在后面
股票问题只要明确每天持有股票的状态,就比较好推导出状态转移关系。