代码随想录算法训练营Day46|动态规划：121.买卖股票的最佳时机I、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

买卖股票的最佳时机I

121. 买卖股票的最佳时机 - 力扣（LeetCode）

之前用贪心算法做过相同的题，这次考虑使用动态规划来完成。

dp[i]表示前i天的最大利润

我们已知每一天的价格price[i]，则dp[i]为每一天的价格price[i]减去当初购买的价格buyprice与dp1[i-1]的较大值。 dp[i] = max(dp[i-1],price[i]-buyprice)。

dp[0]表示收益为0

从前往后递推，注意要更新buyprice的价格为当前遍历过的数据中最小的值。

最后返回dp[price.size()-1]。

其实和贪心差不多，或者说贪心是这里动态规划的变体？

class Solution {
public:int maxProfit(vector<int>& prices) {// 如果价格数组为空，则没有利润，返回0if(prices.size()==0)return 0;// 初始化买入价格为第一天的价格int buyprice = prices[0];// 创建一个动态数组dp，用于存储到第i天为止的最大利润// 初始化dp[0]为0，因为第一天买入卖出没有利润vector<int>dp(prices.size(),0);dp[0]  = 0;// 遍历价格数组，从第二天开始for(int i = 1;i < prices.size();i++){// 更新买入价格为当前价格和之前最低价格中的较小值buyprice = min(buyprice,prices[i]);// 计算如果在今天卖出股票能获得的最大利润// 即取当前价格减去最低买入价格和前一天的最大利润中的较大值dp[i] = max(dp[i-1],prices[i]-buyprice);}// 返回最后一天的最大利润，即整个期间的最大利润return dp[prices.size()-1];}
};

算法的时间复杂度为O(n)，遍历一次数组，空间复杂度同样为O(n)，需要维护一个dp数组。

买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

由于不能同时参与多笔交易，则每天结束，只会存在拥有一支股票和无股票两种情况，由次，创建一个二维的dp数组（n*2的大小），其中dp[i][0]表示当天结束时，手头没有股票的最大利润，dp[i][1]表示当天结束时手头有股票的利润。

考虑推导，手头没有股票有两种情况，一是前一天就没有股票且今天没买，二是前一天有股票，但今天卖了，则dp[i][0] = max(dp[i-1][0],dp[i-1][1]+price[i])，手头有股票同样有两种情况，一是前一天没有股票但今天买了，二是昨天的股票没卖。

dp[i][1] = max(dp[i-1][0] - price[i],dp[i-1][1])

考虑到这样的情况，需对dp[0][0]和dp[1][0]初始化，dp[0][0] = 0,dp[0][1]=-price[0]

从前往后遍历（本质上还是从天来推导）

最后一天由于dp[i][0]一定大于dp[i][1]，返回dp[i][0]即可。

class Solution {
public:int maxProfit(vector<int>& prices) {// 创建一个二维数组dp，行数为prices的大小，列数为2// dp[i][0]代表第i天结束时，不持有股票的最大利润// dp[i][1]代表第i天结束时，持有股票的最大利润vector<vector<int>> dp(prices.size(), vector<int>(2, 0));// 初始化dp数组的第一行// 第一天不持有股票的最大利润为0dp[0][0] = 0; // 第一天持有股票的最大利润为负的第一天价格（即买入股票）dp[0][1] = -prices[0];// 遍历价格数组，从第二天开始更新dp数组for(int i = 1; i < prices.size(); i++){// 更新第i天不持有股票的最大利润// 可以是前一天就不持有股票，或者前一天持有股票但今天卖出dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);// 更新第i天持有股票的最大利润// 可以是前一天就持有股票，或者前一天不持有股票但今天买入dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);}// 返回最后一天不持有股票的最大利润return dp[prices.size()-1][0];}
};

算法的时间复杂度为O(n)，空间复杂度为O(n)。

买卖股票的最佳时机III

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

每天结束后，我们手中持有的股票有以下五种情况。

1. 无操作
2. 第一次买操作
3. 完成一笔操作
4. 第二次买操作
5. 完全两笔交易

由此，我们根据买卖股票的最佳时机II相似的方式，来完成本题。

• dp[i][0]：没有进行任何交易时的利润。

• dp[i][1]：进行了第一次买入后的利润。

• dp[i][2]：完成了第一次卖出后的利润。

• dp[i][3]：进行了第二次买入后的利润。

• dp[i][4]：完成了第二次卖出后的利润。

dp[i][0]始终为0，这里我们将dp[i][0] = do[i-1][0];

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])

dp[i][4] = max(dp[i-1][4],dp[i-1][3] + prices[i])

从前向后遍历

返回dp[prices.size()-1][4]

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0; // 如果没有价格数据，则利润为0vector<vector<int>> dp(prices.size(), vector<int>(5, 0)); // 初始化dp数组// 初始化第一天的状态dp[0][1] = -prices[0]; // 第一天买入股票后的利润dp[0][3] = -prices[0]; // 假设k>=2，第一天买入第二次股票后的利润for (int i = 1; i < prices.size(); i++) { // 遍历价格数组// 更新第i天不进行任何交易的最大利润，这个值始终为0，因为不交易不会有利润变化dp[i][0] = dp[i - 1][0];// 更新第i天进行第一次买入后的最大利润dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);// 更新第i天完成第一次卖出后的最大利润dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);// 更新第i天进行第二次买入后的最大利润dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);// 更新第i天完成第二次卖出后的最大利润dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}// 返回最后一天完成所有交易后的最大利润return dp[prices.size() - 1][4];}
};

算法的时间复杂度为O(n)，空间复杂度为O(n)。