做网站需要什么样的电脑配置,物流托运,电商网站规划与建设方案,新乡 网站开发代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ] 一、121. 买卖股票的最佳时机 链接: 代码随想录. 思路#xff1a;dp[i][0] 第i天持有股票的最大利润 dp[i][1] 第i天不持有股票的最大利润 做题状态#xff1a;…代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ] 一、121. 买卖股票的最佳时机 链接: 代码随想录. 思路dp[i][0] 第i天持有股票的最大利润 dp[i][1] 第i天不持有股票的最大利润 做题状态看解析后做出来了 class Solution {
public:int maxProfit(vectorint 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;vectorvectorint dp(prices.size(), vectorint(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 (vectorint nums : dp) {// cout endl;// for (int i : nums) {// cout i ;// }// }return dp[prices.size() - 1][1];}
};
二、122.买卖股票的最佳时机II 链接: 代码随想录. 思路因为是多次买卖所以每次买卖前要考虑前一天持有状态 做题状态看解析后做出来了 class Solution {
public:int maxProfit(vectorint 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])vectorvectorint dp(prices.size(), vectorint(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(vectorint 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])vectorvectorint dp(prices.size(), vectorint(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];}
};
