动态规划—买卖股票最佳时机-育师

文章目录

一、[题目](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150)
二、My thinking
三、动态规划
- 3.1 动态规划算法
- 3.2 算法步骤
- 3.3 代码实现
- 3.4 时间和空间复杂度
四、总结

一、题目

给定一个数组 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。

二、My thinking

求最大值，但必须是后面元素减前面元素的最大。

挨个遍历，从第一个元素开始，取后面所有元素的最大值与其相减，将得到的差值替换掉第一个元素，以此类推。
最后，求数组中（除了最后一个元素）的最大值

代码实现

classSolution:defmaxProfit(self,prices:list[int])->int:iflen(prices)==1:return0forkinrange(len(prices)-1):if(m:=max(prices[k+1:len(prices)+1]))>prices[k]:prices[k]=m-prices[k]else:prices[k]=0returnmax(prices[0:len(prices)-1])

结果超时了

时间复杂度：两层循环：O(n²)，返回时求最大值：O(n)，总的时间复杂度为： O(n²)+O(n) ≈ O(n²)
空间复杂度：因为用到了切片，总的空间复杂度为：O(n)

三、动态规划

3.1 动态规划算法

动态规划（Dynamic programming， DP）：将一个大问题分解为若干个重叠的子问题，并通过保存子问题的解来避免重复计算，从而高效解决原问题。

核心思想：记住求过的解。

算法步骤（参考：菜鸟教程）：

定义状态：用一个或多个数组（通常叫 dp）来表示子问题的解。关键是弄清楚 dp[i] 或者 dp[i][j] 代表什么含义。
确定状态转移方程：找出 dp[i] 与之前状态（如 dp[i-1], dp[i-2]）之间的关系。这是动态规划的核心和难点。
确定初始条件（Base Case）：最小的、不可再分的子问题的解。这是递推的起点，必须手动定义。
确定计算顺序并计算：确定是"自顶向下"（记忆化递归）还是"自底向上"（循环递推）。

3.2 算法步骤

在本题中，因为要求最大利润，并且后面元素减前面元素。要想得到最大利润，必要要找到一个最低的买入点和最高的卖出点（前提是，买入在前，卖出在后）。
可刚开始我们不知道最低买入点是多少，那就先从第一个开始买，此时利润值0，这相当于确定了初始值，往前走；
如果第二个元素 < 第一个，不卖（卖了就亏了），更新：将此元素确定为最低买入点。如果第二个 > 第一个，卖了（获得利润），更新利润值。往前走；
依次往前遍历，更新最低买入点和利润值。
最后输出利润值。

定义初始值和确定初始条件：最低买入点min_price，从第一个开始，利润值 profit = 0
遍历数组中的元素，并判断是否更新最低买入点和利润值
返回利润值

这样走下来，每个元素就只需要遍历一次就OK了。和暴力超时的算法相比，最大的优化就是：用两个变量记住了之前的状态，每走一步，决定要不要更新优化之前的状态。

3.3 代码实现

classSolution:defmaxProfit(self,prices:list[int])->int:min_price=prices[0]profit=0forpinprices:ifp<min_price:min_price=p# 更新历史最低买入价elifp-min_price>profit:profit=p-min_price# 更新最大利润returnprofit

换成典型一点的动态规划写法：

classSolution:defmaxProfit(self,prices:List[int])->int:inf=int(1e9)minprice=inf# 给第一个元素也行maxprofit=0forpriceinprices:# 下面两行就是状态转移方程，记住了之前的状态，每一步都和之前状态比一比，决定是否优化maxprofit=max(price-minprice,maxprofit)minprice=min(price,minprice)returnmaxprofit 作者：力扣官方题解 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/136684/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

换成二维DP写法：

classSolution:defmaxProfit(self,prices:list[int])->int:n=len(prices)ifn==0:return0# dp[i][0]：第 i 天不持有股票时的最大收益# dp[i][1]：第 i 天持有股票时的最大收益dp=[[0,0]for_inrange(n)]dp[0][0]=0dp[0][1]=-prices[0]# 第 0 天买入，收益为负foriinrange(1,n):# 不持有：昨天就不持有，或今天卖出dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])# 持有：昨天就持有，或今天买入（本题只能买一次，买入价即 -prices[i]）dp[i][1]=max(dp[i-1][1],-prices[i])returndp[n-1][0]