加餐|买卖股票:常见且必考的动态规划面试题
你好,我是卢誉声。
上一课我们介绍了动态规划面试问题中求方案总数和求可行性这两大类问题的通用解法,解题模版如下:
- 根据特征判断是否用动态规划来解;
- 确定初始化状态和状态参数;
- 确定状态存储数组(即备忘录);
- 写出关键的状态转移方程;
- 编写代码进行求解。
这样的解题模版(套路)是可以复用的,希望你能牢牢记住。今天,作为一节加餐课,我想给你介绍另一种常考的面试问题:买卖股票。这种问题的变种比较多,但依然可以用上述解题模版来解决所有买卖股票的问题,从而做到一通百通。