在线购物网站,怎么用新浪云做网站,服务外包有哪些,电商自学网免费# 力扣第40天----第121题、第122题 文章目录 一、第121题--买卖股票的最佳时机二、第122题--买卖股票的最佳时机II 一、第121题–买卖股票的最佳时机
分2种情况考虑#xff0c;根据持有股票、不持有股票这2种情况#xff0c;完成递推公式。另外#xff0c;这里要求只买卖…# 力扣第40天----第121题、第122题 文章目录 一、第121题--买卖股票的最佳时机二、第122题--买卖股票的最佳时机II 一、第121题–买卖股票的最佳时机
分2种情况考虑根据持有股票、不持有股票这2种情况完成递推公式。另外这里要求只买卖一次所以买入的前一个状态一定是手里现金为0。
class Solution {
public:int maxProfit(vectorint prices) { //0表示不持有 1表示持有vectorvectorint dp(2, vectorint(prices.size(), 0));dp[0][0] 0;dp[1][0] -prices[0];for(int i 1; iprices.size(); i){dp[0][i] max(dp[0][i-1], dp[1][i-1] prices[i]);dp[1][i] max( - prices[i], dp[1][i-1] ); //这里控制只买卖一次。如果是别的值不是0就是买卖多次。}return dp[0][prices.size() - 1];}
};二、第122题–买卖股票的最佳时机II
跟上一题基本一样。可以买卖多次那么买入的前一个状态手里可以有现金要根据前一个状态手里现金数再做处理。
class Solution {
public:int maxProfit(vectorint prices) { //0表示不持有 1表示持有vectorvectorint dp(2, vectorint(prices.size(), 0));dp[0][0] 0;dp[1][0] -prices[0];for(int i 1; iprices.size(); i){dp[0][i] max(dp[0][i-1], dp[1][i-1] prices[i]);dp[1][i] max(dp[0][i-1] - prices[i], dp[1][i-1] );}return dp[0][prices.size() - 1];}
};
