加餐｜买卖股票：常见且必考的动态规划面试题
卢誉声
你好，我是卢誉声。
上一课我们介绍了动态规划面试问题中求方案总数和求可行性这两大类问题的通用解法，解题模版如下：
根据特征判断是否用动态规划来解；
确定初始化状态和状态参数；
确定状态存储数组（即备忘录）；
写出关键的状态转移方程；
编写代码进行求解。
这样的解题模版（套路）是可以复用的，希望你能牢牢记住。今天，作为一节加餐课，我想给你介绍另一种常考的面试问题：买卖股票。这种问题的变种比较多，但依然可以用上述解题模版来解决所有买卖股票的问题，从而做到一通百通。
买卖股票问题
在技术面试环节，如果考察动态规划问题的话，那么买卖股票就是一类常考且经典的问题。这类问题一般来说属于求最优解（最大值和最小值）的范畴，下面我们看看这个问题到底是怎样的。
算法问题分析
问题：给定一个数组，它的第 个元素是一支给定的股票在第 天的价格。请你设计一个算法来计算你所能获取的最大利润，你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了动态规划在技术面试中的应用，以买卖股票问题为例进行了详细分析。作者首先讨论了买卖股票问题的特点，指出其适合使用动态规划求解，并引出了状态转移方程的思路。通过分析股票利润与前一天利润的关系，提出了状态转移方程，并给出了Java和C++的代码实现。文章总结了攻破买卖股票问题的解题模板，强调了该类问题的灵活多变性。通过介绍动态规划解题模板和买卖股票问题的分析，为读者提供了解决类似问题的思路和方法。文章内容深入浅出，适合技术面试准备者阅读学习。文章还提供了一个实例化解题模板后的具体问题，以及状态转移方程的详细讲解，为读者提供了实用的技术知识。整体而言，本文对动态规划解题模板和买卖股票问题进行了全面而深入的介绍，为读者提供了宝贵的学习资源。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(5)
- 最新
- 精选
- 我是一把火这道题目的备忘录设计得很巧妙，未持有的情况就是比较'哪天卖出"更好，持有的情况就是比较"哪天买入"更好，不知道我理解的对不对。
作者回复: 从直观上来说的确可以这样理解，核心还是决定当日是否买入卖出的这个决策并根据决策来取最优解。
2020-10-224 
凉人。讲的很棒作者回复: 谢谢！一起学习，加油。
2020-10-083
后视镜老师，我问下关于冷冻期，在 leetcode 309题目，我尝试着用上面的解题公式套入进去的时候发现冷冻期有些疑问，小于 t + 1 天的公式是不是就不适用了？ 我理解 < t +1 天内，只能买卖一次。对于第 i 天持有股票的状态，DP[i][j](i < t+1)，DP[i][1] = max(DP[i-1][1], -prices[i])。 1. 是不是在 < t+1 天只能挑股票最小的一天来持有？ 2. 还是说 < t+1 天都是算是初始状态？作者回复: <t+1天的状态会在计算过程中逐步计算出来，实际上最后的结果就是挑选股票最小的一天持有。
2022-06-28- xuanyuan状态参数的确定还是很难的，状态参数确定有更详细的思考方法吗？
作者回复: 状态参数的确没有更加系统化的思考方法了，这个也就是动态规划最难的地方，但是如果能够理解动态规划的原理，就可以按照一种“感觉”去寻找这些状态参数，其实还是需要多加练习。
2020-11-15 
osun第一题的最大利润是否有更简便的方法，将数组后面减去前面，得到一个差值的数组，然后求最大子数组的和？当然sum肯定是大于等于0的作者回复: 第1题会有两次买入卖出，不可能直接求最大子数组的和，但是可以转换为两个子数组的最大和。但是即使转换一下问题也是需要用动态规划求解的。其实问题本身并没有本质简化。
2020-10-072
收起评论
