本文主要是介绍代码随想录算法训练营Day48 | 121.买卖股票的最佳时机、122.买卖股票的最佳时机 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
121.买卖股票的最佳时机
（想写动态规划写着写着变成贪心了）
半贪心半动规：
int maxProfit(vector<int>& prices) {vector<int> dp(prices.size(), 0);int minVal = prices[0];for (int i = 1; i < prices.size(); ++i) {// 更新最低买入价格if (prices[i] < minVal) {minVal = prices[i];dp[i] = dp[i - 1];}// 尝试卖出elsedp[i] = std::max(dp[i - 1], prices[i] - minVal);}return dp[prices.size() - 1];
}// 利用滚动数组的思路进行优化：
int maxProfit(vector<int>& prices) {int dp = 0;int minVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] < minVal)minVal = prices[i];elsedp = std::max(dp, prices[i] - minVal);}return dp;
}动规写法，重点在于DP数组的定义
1、DP数组定义：
dp[i][j]为当前利润，买入则减，卖出则加
· dp[i][0]表示如果当前持有股票，所能获得的最大利润（持有的股票可以是当天购入的也可以是之前购入的）
· dp[i][1]表示如果当前不持有股票，所能获得的最大利润（可以是还没有购入过也可以是购入后卖出了）2、DP数组初始化：dp[0]初始化为-prices[0]，起步资金为0，所以相当于第一次买入，即 dp[0] = 0 - prices[0]
3、递推公式：
· 对于dp[i][0]：判断当日买入和前几日买入，哪个更便宜，即：
dp[i][0] = max(dp[i - 1][0], -prices[i])
· 对于dp[i][1]：判断当日卖出和前几日卖出，哪个收益更高，即：
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
4、遍历顺序：按时间顺序从前向后遍历
int maxProfit(vector<int>& prices) {dp[0][0] = -prices[0]; // 购入第一支股票dp[0][1] = 0;for (int i = 1; i < prices.size(); ++i) {dp[i][0] = std::max(dp[i - 1][0], -prices[i]);// 卖出：前一天的最大卖出利润 与 前一天持有+今日卖出所得 取较大值dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[prices.size() - 1][1];
}122.买卖股票的最佳时机 II
之前用贪心写过这题
int maxProfit(vector<int>& prices) {vector<int> dp(prices.size(), 0);int curVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] < curVal)dp[i] = dp[i - 1];elsedp[i] = dp[i - 1] + prices[i] - curVal;curVal = prices[i];}return dp[prices.size() - 1];
}// 用滚动数组思路进行写法优化（完全变成了之前的贪心写法）
int maxProfit(vector<int>& prices) {int dp = 0;int curVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] > curVal)dp += prices[i] - curVal;curVal = prices[i];}return dp;
}延续 买卖股票I 思路的动规写法：
与 I 相比，差异在于可以反复买入卖出，即每次买入时的启动资金不是0，而是之前卖出所得的资金总量
差异仅在于dp[i][0]的递推公式：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = -prices[0];for (int i = 1; i < prices.size(); ++i) {// 是否选择今天买入dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 是否选择今天卖出dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[prices.size() - 1][1];
}
这篇关于代码随想录算法训练营Day48 | 121.买卖股票的最佳时机、122.买卖股票的最佳时机 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
