代码随想录算法训练营第五十一天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

本文主要是介绍代码随想录算法训练营第五十一天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第五十一天

121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

1. 确定dp数组以及下标的含义：dp[i][0]：第i天不持有股票的最大利润，dp[i][1]：第i天持有股票的最大利润
2. 确定递推公式：
   1. 第i天不持有有2种情况：前一天持有，当天卖出不持有；前一天不持有，当天也不持有。所以dp[i][0] = max(dp[i-1][1]+prices[i]，dp[i-1][0]）
   2. 第i天持有也有两种情况：前一天持有当天继续持有；前一天不持有，当天买入。所以dp[i][1] = max(dp[i-1][1],-prices[i])。（只买卖一次）
3. dp数组如何初始化：第一天不持有就是dp[0][0] = 0；第一天持有就是第一天买入dp[0][1] = -prices[0]
4. 确定遍历顺序：从前向后遍历。
5. 打印dp数组。

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

---

122.买卖股票的最佳时机II

题目链接：122.买卖股票的最佳时机II

1. 确定dp数组以及下标的含义：dp[i][0]：第i天不持有股票的最大利润，dp[i][1]：第i天持有股票的最大利润
2. 确定递推公式：
   1. 第i天不持有有2种情况：前一天持有，当天卖出不持有；前一天不持有，当天也不持有。所以dp[i][0] = max(dp[i-1][1]+prices[i]，dp[i-1][0]）
   2. 第i天持有也有两种情况：前一天持有当天继续持有；前一天不持有，当天买入。所以dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])。
3. dp数组如何初始化：第一天不持有就是dp[0][0] = 0；第一天持有就是第一天买入dp[0][1] = -prices[0]
4. 确定遍历顺序：从前向后遍历。
5. 打印dp数组。

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

---

这篇关于代码随想录算法训练营第五十一天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---