Facebook 面试题 | 有手续费的买卖股票问题

作者 | 戴助教+本助教

编辑 | Cecily

专栏 | 九章算法

1. 我们考虑最朴素的方法，对于每一天，如果当前有股票，考虑出售或者保留，如果没股票，考虑购买或者跳过，进行dfs搜索。每天都有两种操作，时间复杂度为O(2^n)

2. 如何优化呢？我们用动态规划的思想来解决这个问题，考虑每一天同时维护两种状态：拥有股票(own)状态和已经售出股票(sell)状态。用own和sell分别保留这两种状态到目前为止所拥有的最大利润。 对于sell，用前一天own状态转移，比较卖出持有股是否能得到更多的利润，即sell = max(sell , own + price - fee)， 而对于own , 我们考虑是否买新的股票更能赚钱(换言之，更优惠），own=max( own, sell-price)

3. 初始化我们要把sell设为0表示最初是sell状态且没有profit，把own设为负无穷因为最初不存在该状态，我们不希望从这个状态进行转移

4. 因为我们保存的都是最优状态，所以在买卖股票时候取max能保证最优性不变

5. 最后直接返回sell即可

http://lintcode.com/en/problem/best-time-to-buy-and-sell-stock/