通达信的接口授权-这种动态规划你见过吗状态机动态规划之股票问题

????优质资源分享????

???? Python实战微信订餐小程序 ????	进阶级	本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。
????Python量化交易实战????	入门级	手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

这种动态规划你见过吗——状态机动态规划

买卖股票的最佳时机I

给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

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

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

暴力解法

在这个问题当中，我们的任务是在某一天买入股票，然后在未来某天再将股票卖出去，那么我们就可以用一个二重循环，第一层循环遍历每一天的股票，第二层循环遍历该天之后的股票，然后找到差值最大的那一天即可，也就是寻找某天后面价值最高的股票！通过做差得到差值，将差值最大的返回即可！



|  | class Solution { |
|  | public int maxProfit(int[] prices){ |
|  | int ans = 0; |
|  | for (int i = 0; i < prices.length - 1; i++) { |
|  | for (int j = i + 1; j < prices.length; j++) { |
|  |  ans = Math.max(ans, prices[j] - prices[i]); |
|  |  } |
|  |  } |
|  | return ans; |
|  |  } |
|  |  |
|  | } |

上面的代码的时间复杂度为O，空间复杂度为O，由于时间复杂度过高，上面的代码在Leetcode上面提交会超时。

贪心解法

在暴力解法当中我们思考的是寻找某天后面的最大值，在这个问题当中我们可以换一个角度，就是寻找某天前面股票价值最低的那一天，然后在那一天买进，在当天卖出即可，这个效果和上面暴力解法是一样的。这样的话我们可以用一个数组mins去存某一天前面价值最小的股票，然后做一个减法即可，即prices[i]-mins[i]，这样我们就得到了在第i个位置卖出能够得到的最大的价值，那么我们再比较所有的这些值，我们就可以找到最后的答案了！这样的话我们可以将时间复杂度降低到O。



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int ans = 0; |
|  | int[] mins = new int[prices.length]; |
|  | int min = Integer.MAX\_VALUE; |
|  | for (int i = 0; i < prices.length; i++) { |
|  |  min = Math.min(min, prices[i]); |
|  |  mins[i] = min; |
|  |  } |
|  | for (int i = 0; i < prices.length; i++) { |
|  |  ans = Math.max(ans, prices[i] - mins[i]); |
|  |  } |
|  | return ans; |
|  |  } |
|  | } |

上面的代码的时间复杂度为O，空间复杂度也是O，其实仔细思考一下我们还可以降低空间复杂度：



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int low = Integer.MAX\_VALUE; |
|  | int ans = 0; |
|  | for (int i = 0; i < prices.length; i++) { |
|  |  low = Math.min(prices[i], low); |
|  |  ans = Math.max(ans, prices[i] - low); |
|  |  } |
|  | return ans; |
|  |  } |
|  | } |

我们在第一次遍历的时候可以用一个值low保存第i个位置左边最小的值即可，并且在遍历的过程当中不断更新low值，而且我们在遍历的时候可以顺便求出对应位置的能够获取的最大价值，可以避免第二次遍历。在这个情况下我们的时间复杂度为O，空间复杂度为O。

动态规划解法

在求解动态规划问题的时候通常的步骤有以下几个：

寻找能够表示状态的数组dp，即我们需要寻找dp的含义，分析需要用几纬数组表示具体的状态。通过分析问题，寻找动态转移公式。初始化状态数组。通过分析动态转移方程，确定数组的遍历顺序。

状态表示数组

在这个问题当中我们用一个二维数组去表示我们的状态，在这个问题当中主要有两个状态，一个是手上有股票，另一是手上没有股票：

dp[i][0]表示在第i天手上没有股票能够获得的最大的收益，比如我们在第一天的没有股票的收益为0元。dp[i]表示在第i天手上存在股票能够获得的最大的收益，比如我们在第一天买入股票之后收益为-prices[0]。

那么我们最后的答案是dp[N][0]，这个表示在最后一天，我们的手中不存在股票，即我们将股票卖出去能够获取的最大的收益。

状态转移方程

现在我们来分析一下如何进行状态的转移：

dp[i][0]的状态如何从第i-1的状态转移过来：如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0]=dp[i-1][0]，因为没有进行交易。如果第i-1个状态手中存在股票，即dp[i-1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1]+prices[i]，即dp[i][0]=dp[i-1]+prices[i]。综合上面的两种转移方式可以得到下面的转移方程：dp[i][0]=maxdp[i]的状态如何进行转移：如果第i-1个状态是手中不存在股票，即dp[i-1][0]，而第i个状态有股票，那么dp[i][0]=-prices[i]，因为买入股票，而且只能够买入一次，因此直接等于-prices[i]即可，注意这里不能是dp[i-1][0]-prices[i]，因为在dp[i-][0]当中可能存在先买入再卖出的情况，而题干要求只能买入卖出一次。如果第i-1个状态手中存在股票，即dp[i-1]，而第i个状态有股票，因此不需要进行交易，即dp[i]=dp[i-1]。综合上面的两种转移方式可以得到下面的转移方程：dp[i]=max;整个状态转移过程如下所示：

上面所谈到的有两种状态，一种是有股票，一种是没有股票，这两种状态需要从第i-1行转移到第i行，即从第i-1行的有股票和无股票状态转移到第i行的有股票和无股票状态，这就是我们在前文谈到的状态机，我们已经有了状态，而且也有了状态之间的转换，这就是状态机动态规划。你可能会问这好像跟之前传统的动态规划区别也不是太大啊，这是因为在这个问题当中只有两个状态，我们在下篇当中遇到的问题就会有多个状态了，在那个时候你可能就更加理解为什么称这种动态规划叫做状态机动态规划了。

综合两种状态，整个转移方式如下：

{dp[i][0]=maxdp[i]=max;整个代码如下：



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int[][] dp = new int[prices.length][2]; |
|  | // 初始化数组 dp[0][0] 默认等于0 不用 |
|  | // 显示初始化 |
|  |  dp[0][1] = -prices[0]; |
|  | for (int i = 1; i < prices.length; i++) { |
|  |  dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); |
|  |  dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); |
|  |  } |
|  | return dp[prices.length - 1][0]; |
|  |  } |
|  | } |

数组优化

我们可以仔细分析一下上面的状态转移方程，可以发现第i行，只依赖第i-1行，因此我们只使用两行数组即可，第一行推测出第二行，第二行推测出来的结果再存回第一行…



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int[][] dp = new int[2][2]; |
|  |  dp[0][1] = -prices[0]; |
|  | for (int i = 1; i < prices.length; i++) { |
|  |  dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]); |
|  |  dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], -prices[i]); |
|  |  } |
|  | return dp[(prices.length - 1) % 2][0]; |
|  |  } |
|  | } |

可以使用位运算稍微优化一下：



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int[][] dp = new int[2][2]; |
|  |  dp[0][1] = -prices[0]; |
|  | for (int i = 1; i < prices.length; i++) { |
|  |  dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]); |
|  |  dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], -prices[i]); |
|  |  } |
|  | return dp[(prices.length - 1) & 1][0]; |
|  |  } |
|  | } |

最终经过上面的优化动态规划的时间和空间复杂度可以优化到O和O。

买卖股票的最佳时机II

给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

示例1:输入：prices=[7,1,5,3,6,4]输出：7解释：在第2天的时候买入，在第3天的时候卖出,这笔交易所能获得利润=5-1=随后，在第4天的时候买入，在第5天的时候卖出,这笔交易所能获得利润=6-3=总利润为4+3=

示例输入：prices=[1,2,3,4,5]输出：4解释：在第1天的时候买入，在第5天的时候卖出,这笔交易所能获得利润=5-1=总利润为

这道题和第一题的区别就是，在这道题当中你可以买卖股票多次，但是最多只能持有一只股票，因此这道题和第一题的大多数情况是相同的。

状态表示数组

在这个问题当中我们用一个二维数组去表示我们的状态，在这个问题当中主要有两个状态，一个是手上有股票，另一是手上没有股票：

那么我们最后的答案是dp[N][0]，这个表示在最后一天，我们的手中不存在股票，即我们将股票卖出去能够获取的最大的收益。

状态转移方程

现在我们来分析一下如何进行状态的转移：

dp[i][0]的状态如何从第i-1的状态转移过来：如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0]=dp[i-1][0]，因为没有进行交易。如果第i-1个状态手中存在股票，即dp[i-1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1]+prices[i]，即dp[i][0]=dp[i-1]+prices[i]。综合上面的两种转移方式可以得到下面的转移方程：dp[i][0]=maxdp[i]的状态如何进行转移：如果第i-1个状态是手中不存在股票，即dp[i-1][0]，而第i个状态有股票，这道题目和上一道题目只有这个地方是不一致的，在上一道题当中dp[i][0]=-prices[i]，这是因为只能够买入股票一次，具体原因是在dp[i-1][0]当中可以存在股票买入，而且已经卖出这种情况，而第一题只能买入卖出一次，而在这道题目当中，能够买卖股票多次，因此dp[i][0]=dp[i-1][0]-prices[i]。如果第i-1个状态手中存在股票，即dp[i-1]，而第i个状态有股票，因此不需要进行交易，即dp[i]=dp[i-1]。综合上面的两种转移方式可以得到下面的转移方程：dp[i]=max;综合上面的两个状态：



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int[][] dp = new int[2][2]; |
|  |  dp[0][1] = -prices[0]; |
|  | for (int i = 1; i < prices.length; i++) { |
|  |  dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]); |
|  |  dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]); |
|  |  } |
|  | return dp[(prices.length - 1) & 1][0]; |
|  |  } |
|  | } |

贪心解法

因为我们可以无数次买入卖出，因此只要存在前一天的价格低于今天的价格，那么我们就可以在前一天买入，在今天卖出，在这种情况下我们的收益就是最大的，因为我们抓住了“每一次赚钱的机会”。

比如prices=[1,2,3]，我们的收益就等于+=这个过程相当于在第一天买入，第二天卖出，第二天再买入，第三天卖出。又比如prices=[4,5,3,6]，我们的收益等于+0+=这个过程相当于第一天买入第二天卖出，第三天再买入第四天卖出。

代码如下：



|  | class Solution { |
|  | public int maxProfit(int[] prices) { |
|  | int ans = 0; |
|  | int n = prices.length; |
|  | for (int i = 1; i < n; ++i) { |
|  |  ans += Math.max(0, prices[i] - prices[i - 1]); |
|  |  } |
|  | return ans; |
|  |  } |
|  | } |
|  |  |

文章为作者独立观点，不代表观点