怎么做网站需要多少钱,域名要多少钱,太原建站seo,建设银行网站怎么开通短信服务121. 买卖股票的最佳时机
题目链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
求解思路#xff1a;
动规五部曲
确定dp数组及其下标含义#xff1a;使用一个二维数组dp[i][2]#xff0c;dp[i][0]代表持有股票的最大收益
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
动规五部曲
确定dp数组及其下标含义使用一个二维数组dp[i][2]dp[i][0]代表持有股票的最大收益dp[i][1]代表不持有股票的最大收益注意“持有”不代表当天买入可能是之前的某一天就买入了“不持有”同理确定递推公式如果当天持有股票则股票可能是之前就买好了或者是当天买的递推公式取两者较大值即dp[i][0] max(dp[i - 1][0], -prices[i])如果当天不持有股票则股票可能是之前就卖出了也可能是当天才卖出取两者较大值即dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);dp数组的初始化dp[0][0]表示第0天持有股票dp[0][0] - prices[0]dp[0][1]表示第0天不持有股票dp[0][1] 0确定遍历顺序从前向后举例推导dp数组以[7,1,5,3,6,4]为例dp数组状态如下 代码
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(),vectorint(2));// 0为当天持有该股票1为当天不持有dp[0][0] -1 * prices[0];dp[0][1] 0;for (int i 1; i prices.size(); i){// 当天持有股票可能是之前买的可能是今天买的dp[i][0] max(dp[i-1][0], -1 * prices[i]);// 当天未持有股票可能是之前卖了也可能是今天卖了dp[i][1] max(dp[i-1][1], prices[i] dp[i-1][0]);}return dp[prices.size()-1][1];}
};
122.买卖股票的最佳时机II
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
和前一题唯一不一样的地方在于当天持有股票的所得金额即dp[i][0]的递推公式
如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来第i-1天就持有股票则保持现状即dp[i][0] dp[i-1][0]第i天买入股票则所得现金为昨天不持有股票的现金减去今天的股票价格即 dp[i - 1][1] - prices[i]
代码
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 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][1];}
};
