代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ]
代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ]
一、121. 买卖股票的最佳时机
链接: 代码随想录.
思路：dp[i][0] 第i天持有股票的最大利润 dp[i][1] 第i天不持有股票的最大利润
做题状态：看解析后做出来了
class Solution {
public:int maxProfit(vector<int>& prices) {// dp[i][0] 第i天 持有 股票的状态得到的最大利润// dp[i][1] 第i天 不持有 股票的状态得到的最大利润// 一直持有，就是前一天的持有状态 dp[i-1][0]// 或者我现在买了才持有，因为只能买卖一次，所以是-prices[i]// dp[i][0] = max(dp[i-1][0],-prices[i])// 一直不持有，就是前一天的不持有状态 dp[i-1][1]// 或者我现在卖了才不持有，所以是前一天持有状态+卖掉的前// dp[i-1][0]+price[i] dp[i][1] = max(dp[i-1][1],dp[i-1][0]+price[i])// 初始化 dp[0][0] = -prices[i]// dp[0][1] = 0;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] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}// for (vector<int> nums : dp) {// cout << endl;// for (int i : nums) {// cout << i << " ";// }// }return dp[prices.size() - 1][1];}
};二、122.买卖股票的最佳时机II
链接: 代码随想录.
思路：因为是多次买卖，所以每次买卖前要考虑前一天持有状态
做题状态：看解析后做出来了
class Solution {
public:int maxProfit(vector<int>& prices) {// dp[i][0] 第i天不持有 最大利润// dp[i][1] 第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])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], dp[i - 1][0] - prices[i]);}return dp[prices.size()-1][0];}
};三、123.买卖股票的最佳时机III
链接: 代码随想录.
思路：注释
做题状态：看解析后做出来了
class Solution {
public:int maxProfit(vector<int>& prices) {// dp[i][j] i 代表第i天// j有五种情况 0—无操作 1-第一次持有 2-第一次卖出 3-第二次持有 4-第二次卖出// dp[i][0] = dp[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])vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[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]);}return dp[prices.size() - 1][4];}
};