这段时间在复刷题目同时也在做新的相关题目。感觉自己对动态规划题目还是不能掌握。动态规划题目真的是千变万化，很难总结出一条可以一劳永逸的规律。难怪这样的题目会成为大公司的门槛，因为确实不好做啊。我对动态规划的理解，很基础，相比做过类似题目的小伙伴也都是这样。动态规划说白了是为了节省时间复杂度而产生的，也可以说是将需要重复运算的结果存到缓存里，下次需要做同样计算的时候只需要直接从缓存里那结果就好而不再需要重复计算，不要小看这样的改变。举个例子，斐波那契数列的时间复杂度是o(2^n)，通过使用动态规划可以将性能优化到o(n)。
通常，动态规划的题目，一般分为三个步骤。
- 首先根据输出的需要，找到base case, 一般来说，base case是最显而易见的输出结果，创建一个数组用来记录输出。
- 有了base case就需要借机拓展，这时候需要一定的推理，找到前后输出的关联性。根据之前输出来更新当前输出。
- 从输出数组中，找到对应的结果。
估计小伙伴们，大概也都是这样想的。
那么，动态规划为什么难呢？我认为有以下几点：
- 很多题目将动态规划包装的很隐蔽，遇到题目的时候会比较难想到动态规划。
- 推理难，大部分人思考方式是线性的，遇到一些非线性的动态规划题目，就会比较难推理出前后输出的关联性。例如当动态规划和树这种结构结合一般来说都会比较难。这时候大概最好的方法就是拿起笔，在纸上把结果一点一点写出来，直到你发现规律为止。
- 动态规划的题目有时候并不仅仅用到动态规划，所谓的隐性动态规划才是真正的杀手。比如说结合了BFS和动态规划，或者DFS和动态规划，一不小心就会让你的推理跑偏。
- 动态规划很容易陷入到暴力破解的陷阱。
这几年大厂考动态规划的频率颇高，大概是因为想要提高门槛吧。leetcode论坛里时不时有人会透漏一些动态规划的面试题，对于比较初级的面试者来讲还是很有挑战性的。
遇到动态规划题目怎么办？
我个人认为主要看平日练习和对基础的掌握
- 大量的练习可以让你更快的找到前后输出的关联性。
- 一定要用笔演算，这样可以减少推理时候出现的错误，让输出更直观。
- 如果有可能尽量把它和生活联系起来。
平日
做大量的练习积累做题经验，然后总结概括，一定要能啃硬骨头。把每道题吃透，确保遇到类似的题可以做出来。