深圳做三网合一网站,互联网公司薪酬体系,服装定制营销,绍兴网站建设模板网站leetcode121#xff1a;买卖股票的最佳时机 文章讲解#xff1a;leetcode121 leetcode122#xff1a;买卖股票的最佳时机2 文章讲解#xff1a;leetcode122 目录
1#xff0c;leetcode121 买卖股票的最佳时机
2#xff0c;leetcode122 买卖股票的最佳时机2 1#xff0… leetcode121买卖股票的最佳时机 文章讲解leetcode121 leetcode122买卖股票的最佳时机2 文章讲解leetcode122 目录
1leetcode121 买卖股票的最佳时机
2leetcode122 买卖股票的最佳时机2 1leetcode121 买卖股票的最佳时机
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 0; i prices.size(); i) {for (int j i 1; j prices.size(); j){result max(result, prices[j] - prices[i]);}}return result;}
};
贪心拿下
动态规划的思路比较绕 dp[i][0] 表示第i天持有股票所得最多现金 这里可能有同学疑惑本题中只能买卖一次持有股票之后哪还有现金呢 其实一开始现金是0那么加入第i天买入股票现金就是 -prices[i] 这是一个负数。 dp[i][1] 表示第i天不持有股票所得最多现金 这个递推数组是一个二位的但是第二个维度就是区分买不买入当天股票。我的理解是因为股票的收益要从后面才能看出来因此不能简单的在当前位置求max需要记录一下。 如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来 第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0]第i天买入股票所得现金就是买入今天的股票后所得现金即-prices[i] 那么dp[i][0]应该选所得现金最大的所以dp[i][0] max(dp[i - 1][0], -prices[i]); 如果第i天不持有股票即dp[i][1] 也可以由两个状态推出来 第i-1天就不持有股票那么就保持现状所得现金就是昨天不持有股票的所得现金 即dp[i - 1][1]第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金即prices[i] dp[i - 1][0] 同样dp[i][1]取最大的dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]); 这样递推公式我们就分析完了 本题中不持有股票状态所得金钱一定比持有股票状态得到的多 是否持有是个关键。是否持有也对应着买入/卖出或者保持现状。
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();if (len 0) return 0;vectorvectorint dp(len, vectorint(2));dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);}return dp[len - 1][1];}
};
这个dp数组的含义还是很巧妙的。
2leetcode122 买卖股票的最佳时机2
唯一区别就是注意一下可以重复买入因此要和前一天的利润求max
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(2, 0));dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; 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[len - 1][1];}
};
从思路上来说贪心是更容易想到更简单的做法。