[LeetCode]动态规划问题--股票买卖最佳时机

博主: 漫画无聊的冰块

LeetCode中很重要的一类算法是动态规划（DP：dynamic programming），典型的有背包问题、股票买卖最佳时机问题。
这类问题大概路数是这样：什么时候出手获益最大？背包放什么东西最合算？一定条件下要怎么操作才能损失最小？等等这类“求极值”问题。
这类问题的解法一般是这样： 倒着想，从最后一次出手/交易/动作开始算起，分别考虑 出手 | 不出手 的情况下最大获利，往前递推。

具体来讲，先给个引导问题：斐波那契数列求第n项值

fib = 1， 1， 2， 3， 5，8， 13 ...

很熟悉了哈，怎么求 fib(n) 应该也是轻车熟路了。

我们先不上代码，因为按学习经验来讲，原理没吃透就上代码，往往越看越难受。上个分解图先：

分解图
我们知道哈，这种问题递归写起来最舒服，最符合人类直觉，但是会有大量重复计算，就体现在类似 fib(5)这种点上。这种搞法复杂度就爆炸了，达到 O(2^n)。那正常的思路想，我把这些数从小到大计算的时候都给存起来，用的时候去数组取一下不就行了。Bingo~~ (PS:感兴趣去看一下记忆化搜索)

参考文档：
B站：动态规划(第一讲)
OI Wiki: 记忆化搜索