兼职做Ppt代抄论文的网站,网站开发项目成本分析之合理性,wordpress魔方,一条龙网站建设目录
121.买卖股票的最佳时机
暴力法
贪心法
动态规划法
122.买卖股票的最佳时机II
动态规划法
123.买卖股票的最佳时机III
动态规划法 121.买卖股票的最佳时机 题目链接#xff1a;121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09; 文章讲解#…目录
121.买卖股票的最佳时机
暴力法
贪心法
动态规划法
122.买卖股票的最佳时机II
动态规划法
123.买卖股票的最佳时机III
动态规划法 121.买卖股票的最佳时机 题目链接121. 买卖股票的最佳时机 - 力扣LeetCode 文章讲解代码随想录
暴力法 解题思路 找最优间距 代码一暴力法
// 时间复杂度O(n^2)
// 空间复杂度O(1)
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;}
};
贪心法 解题思路 因为股票就买卖一次那么贪心的想法很自然就是取最左最小值取最右最大值那么得到的差值就是最大利润。 代码一贪心法
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:int maxProfit(vectorint prices) {int low INT_MAX;int result 0;for (int i 0; i prices.size(); i) {low min(low, prices[i]); // 取最左最小价格result max(result, prices[i] - low); // 直接取最大区间利润}return result;}
};
动态规划法 解题思路 确定dp数组dp table以及下标的含义dp[i][0] 表示第i天持有股票所得最多现金 本题中只能买卖一次持有股票之后哪还有现金呢其实一开始现金是0那么加入第i天买入股票现金就是 -prices[i] 这是一个负数。dp[i][1] 表示第i天不持有股票所得最多现金注意这里说的是“持有”“持有”不代表就是当天“买入”也有可能是昨天就买入了 代码一动态规划
// 版本一
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];}
};
122.买卖股票的最佳时机II 题目链接122. 买卖股票的最佳时机 II - 力扣LeetCode 文章讲解代码随想录
动态规划法 解题思路 本题和121. 买卖股票的最佳时机 (opens new window)的唯一区别是本题股票可以买卖多次了注意只有一只股票所以再次购买前要出售掉之前的股票 在动规五部曲中这个区别主要是体现在递推公式上其他都和买卖股票的最佳时机 (opens new window)一样一样的。 解题步骤 dp数组的含义dp[i][0] 表示第i天持有股票所得现金。dp[i][1] 表示第i天不持有股票所得最多现金。 如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来注意这里和买卖股票的最佳时机 (opens new window)唯一不同的地方就是推导dp[i][0]的时候第i天买入股票的情况。在买卖股票的最佳时机 (opens new window)中因为股票全程只能买卖一次所以如果买入股票那么第i天持有股票即dp[i][0]一定就是 -prices[i]。而本题因为一只股票可以买卖多次所以当第i天买入股票的时候所持有的现金可能有之前买卖过的利润。那么第i天持有股票即dp[i][0]如果是第i天买入股票所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即dp[i - 1][1] - prices[i]。 第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0] 第i天买入股票所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即dp[i - 1][1] - prices[i] 第i天不持有股票即dp[i][1]的情况 依然可以由两个状态推出来注意这里和121. 买卖股票的最佳时机 (opens new window)就是一样的逻辑卖出股票收获利润可能是负值天经地义 第i-1天就不持有股票那么就保持现状所得现金就是昨天不持有股票的所得现金 即dp[i - 1][1] 第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金即prices[i] dp[i - 1][0] 代码一动态规划
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]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[len - 1][1];}
};
123.买卖股票的最佳时机III 题目链接123. 买卖股票的最佳时机 III - 力扣LeetCode 文章讲解代码随想录
动态规划法 解题思路 这道题目相对 121.买卖股票的最佳时机 (opens new window)和 122.买卖股票的最佳时机II (opens new window)难了不少。关键在于至多买卖两次这意味着可以买卖一次可以买卖两次也可以不买卖 解题步骤 dp[i][j]中 i表示第i天j为 [0 - 4] 五个状态dp[i][j]表示第i天状态j所剩最大现金。需要注意dp[i][1]表示的是第i天买入股票的状态并不是说一定要第i天买入股票这是很多同学容易陷入的误区。例如 dp[i][1] 并不是说 第i天一定买入股票有可能 第 i-1天 就买入了那么 dp[i][1] 延续买入股票的这个状态。 确定dp数组以及下标的含义一天一共就有五个状态 没有操作 其实我们也可以不设置这个状态 第一次持有股票 第一次不持有股票 第二次持有股票 第二次不持有股票 确定递推公式达到dp[i][1]状态有两个具体操作 那么dp[i][1]究竟选 dp[i-1][0] - prices[i]还是dp[i - 1][1]呢 一定是选最大的所以 dp[i][1] max(dp[i-1][0] - prices[i], dp[i - 1][1]); 同理dp[i][2]也有两个操作 所以dp[i][2] max(dp[i - 1][1] prices[i], dp[i - 1][2]) 同理可推出剩下状态部分 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]); 操作一第i天买入股票了那么dp[i][1] dp[i-1][0] - prices[i] 操作二第i天没有操作而是沿用前一天买入的状态即dp[i][1] dp[i - 1][1] 操作一第i天卖出股票了那么dp[i][2] dp[i - 1][1] prices[i] 操作二第i天没有操作沿用前一天卖出股票的状态即dp[i][2] dp[i - 1][2] dp数组如何初始化第0天没有操作这个最容易想到就是0即dp[0][0] 0;第0天做第一次买入的操作dp[0][1] -prices[0];第0天做第一次卖出的操作这个初始值应该是多少呢此时还没有买入怎么就卖出呢 其实大家可以理解当天买入当天卖出所以dp[0][2] 0;第0天第二次买入操作初始值应该是多少呢应该不少同学疑惑第一次还没买入呢怎么初始化第二次买入呢第二次买入依赖于第一次卖出的状态其实相当于第0天第一次买入了第一次卖出了然后再买入一次第二次买入那么现在手头上没有现金只要买入现金就做相应的减少。所以第二次买入操作初始化为dp[0][3] -prices[0];同理第二次卖出初始化dp[0][4] 0; 确定遍历顺序从递归公式其实已经可以看出一定是从前向后遍历因为dp[i]依靠dp[i - 1]的数值。 举例推导dp数组 代码一动态规划
// 版本一
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0];dp[0][3] -prices[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];}
};
