欢迎光临
我们一直在努力

买卖股票最佳时机1动态规划(使用动态规划算法来预测买卖股票的最佳时机)

通知:我已经将刷题指南全部整理到了Github :https://github.com/youngyangyang04/leetcode-master,方便大家在电脑上阅读,这个仓库每天都会更新,大家快去给一个star支持一下吧!

121. 买卖股票最佳时机

题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

思路

暴力

这道题目最直观的想法,就是暴力,找最优间距了。

class Solution {public: int maxProfit(vector& 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^2)
  • 空间复杂度:O(1)

当然该方法超时了。

贪心

因为股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。

C++代码如下:

class Solution {public: int maxProfit(vector& 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; }};

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

动态规划

动规五部曲分析如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][0] 表示第i天持有股票所得现金 ,这里可能有同学疑惑,本题中只能买卖一次,持有股票之后哪还有现金呢?

其实一开始现金是0,那么加入第i天买入股票现金就是 -prices[i], 这是一个负数。

dp[i][1] 表示第i天不持有股票所得现金

注意这里说的是“持有”,“持有”不代表就是当天“买入”!也有可能是昨天就买入了,今天保持持有的状态

很多同学把“持有”和“买入”没分区分清楚。

在下面递推公式分析中,我会进一步讲解。

  1. 确定递推公式

如果第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]);

这样递归公式我们就分析完了

  1. dp数组如何初始化

由递推公式 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[0][0]和dp[0][1]推导出来。

那么dp[0][0]表示第0天持有股票,此时的持有股票就一定是买入股票了,因为不可能有前一天推出来,所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票,不持有股票那么现金就是0,所以dp[0][1] = 0;

  1. 确定遍历顺序

从递推公式可以看出dp[i]都是有dp[i – 1]推导出来的,那么一定是从前向后遍历。

  1. 举例推导dp数组

以示例1,输入:[7,1,5,3,6,4]为例,dp数组状态如下:

买卖股票最佳时机1动态规划

dp[5][1]就是最终结果。

为什么不是dp[5][0]呢?

因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多!

以上分析完毕,C++代码如下:

// 版本一class Solution {public: int maxProfit(vector& prices) { int len = prices.size(); vector> dp(len, vector(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]; }};

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

从递推公式可以看出,dp[i]只是依赖于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状态就可以了,可以使用滚动数组来节省空间,代码如下:

// 版本二class Solution {public: int maxProfit(vector& prices) { int len = prices.size(); vector> dp(2, vector(2)); // 注意这里只开辟了一个2 * 2大小的二维数组 dp[0][0] -= prices[0]; dp[0][1] = 0; for (int i = 1; i < len; i++) { dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]); dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]); } return dp[(len - 1) % 2][1]; }};

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

这里能写出版本一就可以了,版本二虽然原理都一样,但是想直接写出版本二还是有点麻烦,容易自己给自己找bug。

所以建议是先写出版本一,然后在版本一的基础上优化成版本二,而不是直接就写出版本二。

PDF开放下载

以下资源由「代码随想录」原创出品!

  • 回溯算法学习手册开放下载链接: https://pan.baidu.com/s/1p0uvcKb5GRoVgEI2C1CD5Q 密码: smbf
  • 二叉树学习手册开放下载链接: https://pan.baidu.com/s/1fcweZCJK3K8G0FR-nZhr7A 密码: 75en
  • 贪心算法学习手册开放下载链接: https://pan.baidu.com/s/1w8nUdBmGWqyv0g_fwlAINg 密码: 1dl3

(Carl将陆续整理各个专题的PDF下载版本)

力扣刷题指南:https://github.com/youngyangyang04/leetcode-master

这里每天8:35准时推送一道经典算法题目,我选择的每道题目都不是孤立的,而是由浅入深,环环相扣,帮你梳理算法知识脉络,轻松学算法!

@代码随想录 期待你的关注

赞(0) 打赏
未经允许不得转载:股票知识平台 » 买卖股票最佳时机1动态规划(使用动态规划算法来预测买卖股票的最佳时机)
分享到: 更多 (0)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏