《LeetCode》—— 买卖股票的最佳时机
温馨提示：这篇文章已超过461天没有更新，请注意相关的内容是否还可用！
本期，我将给大家讲解的是有关动态规划类的题——买卖股票的最佳时机。这个系列总共有四道题。接下来，让我们一起去看看！！！
目录
（一）买卖股票的最佳时机
（二）买卖股票的最佳时机 II
（三）买卖股票的最佳时机 III
（四）买卖股票的最佳时机 IV
（一）买卖股票的最佳时机
LeetCode题目链接：买卖股票的最佳时机
题目如下：
题目分析：
第一题，我们先来看最简单的（题目的难度也是逐级提升的）。
- 思路一：
首先，我们有的小伙伴一读题，最先想到的可能就是暴力去求解这道题目，但是很遗憾当我们提交代码的时候显示的是代码超时了。因此，很显然暴力解法显然不是出题者要考察我们的地方。
- 思路二：
那么暴力求解不行，还有没有其他思路呢？我们通过分析题目，主要意思就是找到最多一次买卖股票可以获得的最大利润的问题的解决方案。我们可以利用贪心的思路来分析，主要原理是跟踪到目前为止看到的最低价格和以当前价格卖出可以获得的最大利润，通过迭代价格并相应地更新这些值，我们可以找到可以获得的最大利润。
- 思路三：
那么除了上述的贪心去求解还有没有其他思路呢？其实还有一种我们今天主要讲的动态规划算法。
解题思路：
在这里，我只给出动态规划的具体实现过程。
- step1：确定【arry】数组以及下标的含义
首先，我们初始化一个二维数组 arry，其中大小是价格向量的大小（size为给出的数组 prices 的大小），arry 中每行的第一个元素表示买入或者卖出的天数，第二个元素表示当天的状态。
arry[i][0]：
- 表示第i天持有股票所得最多现金 。因为刚开始时没钱买，所以开始现金是0，因此第i天买入股票现金就是 -prices[i]， 这是一个负数；
- arry[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以arry[0][0] -= prices[0];
arry[i][1]：
- 表示第i天不持有股票所得最多现金，即也许是一直都还没有没有买入，或者要卖出；
- arry[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以arry[0][1] = 0;
- step2：确定递推公式
如果第i天持有股票即arry[i][0]， 那么递归公式可以像如下这样：
- 如果在当前前的前一天即（ i-1） 天就持有股票的话，那么当前所持有的现金就是昨天持有股票的所得现金 即：arry[i - 1][0]
- 如果是在当前这一天买入股票即（i），那么此时所持有的就是买入今天的股票后所得现金即：-prices[i]（为负数）
💨 arry[i][0] = max(arry[i - 1][0], -prices[i])
如果第i天不持有股票即arry[i][1]， 那么递归公式可以像如下这样：
- 如果在第（i-1）天未持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：arry[i - 1][1]
- 如果在第（ i ）天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + arry[i - 1][0]
💨 arry[i][1] = max(arry[i - 1][1], prices[i] + arry[i - 1][0])
- step3：确定遍历顺序
从递推公式可以看出arry[i]都是由arry[i - 1]推导出来的，因此是从前向后遍历
- step4：图解展示
代码展示：
- 暴力解法：
class Solution { public: int maxProfit(vector& prices) { int n = (int)prices.size()； int res = 0; for (int i = 0; i性能分析：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 贪心算法：
class Solution { public: int maxProfit(vector& prices) { int num = INT_MAX; int res = 0; for (int i = 0; i性能分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 动态规划：
class Solution { public: int maxProfit(vector& prices) { int size = prices.size(); if (size == 0) return 0; vector arry(size, vector(2)); arry[0][0] -= prices[0]; arry[0][1] = 0; for (int i = 1; i性能分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
（二）买卖股票的最佳时机 II
LeetCode题目链接：买卖股票的最佳时机 II
题目如下：
题目分析：
大家通过分析这道题，我们可以发现这道题跟上道题目的差别就在于本题股票可以进行多次的买卖操作（注意只有一只股票，所以再次购买前要出售掉之前的股票）。
- 思路一：
小伙伴们看到这道题目想的就是 -- 选一个低的买入，再选个高的卖，再选一个低的买入.....循环反复。
其实，我们对这种思路进行分解 -- 只收集正利润，即最终的最大利润就是各天的正利润之和。
对于每次迭代，我们可以计算出价格向量中当前元素与前一个元素之间的差值，并取该差值和0中较大的值，这样做确保仅将正差异添加到 res 变量中，仅使用单个循环来迭代价格向量并计算最大利润
- 思路二：
还是利用动态规划的思想对其进行操作。
解题思路：
因为本题跟上一题是类似的，不同的在关于递推公式，接下来，我就只讲递推公式的演化，其余的跟上题相同。
如果第i天持有股票即arry[i][0]， 那么递归公式可以像如下这样：
这题因为是可以进行多次的买卖的，因此递归公式主要的变化就发生在对于 arry[i][0] 的处理，所以当第（i）天买入股票的时候，所持有的现金可能是在这之前已经经过买卖交易所得到的。
因此，对于第（i）天持有股票即 arry[i][0]：如果是第（i）天买入股票，所得现金就是昨天不持有股票的所得现金 减去 当天的股票价格 即：arry[i - 1][1] - prices[i]。
💨 arry[i][0] = max(arry[i - 1][0], arry[i - 1][1] - prices[i])
如果第i天持有股票即arry[i][1]， 递归公式跟上题相同
💨 arry[i][1] = max(arry[i - 1][1], prices[i] + arry[i - 1][0])
代码展示：
- 贪心算法：
class Solution { public: int maxProfit(vector& prices) { int res=0; for(int i=1; i
- 贪心算法：
- 思路二：
- 思路一：
- 动态规划：
- 贪心算法：
- 暴力解法：
- step4：图解展示
- step3：确定遍历顺序
- step2：确定递推公式
- step1：确定【arry】数组以及下标的含义
- 思路三：
- 思路二：
