动态规划（持续更新）

2020校招真的是。。。10道笔试题起码有一大半都是动态规划。
为了offer，在此整理一下所遇到的dp实例问题的集合。

首先，什么样的问题可以称为动态规划问题：
1.拥有最优的子结构
A.一个大问题的最优解可以通过求解其子问题，递归地去求得子问题的最优解来求得。
2.存在重叠的子问题的情况
A.子问题存在重叠，即相同的子问题的情况，可以记忆该子问题的解，以便后续使用。
一个典型的例子就是斐波那契数列的递归方式求解中f(n)=f(n-1)+f(n-2),存在多个子问题(通项)的情况。用动态规划的话就能存储子问题的解，而不必重新对子问题再去递归求解。
B.需要减少时间复杂度。
斐波那契数列的递归方式时间复杂度是O(2^n),动态规划的话，使用数组存储每个子问题对应索引位置的f(n)，先前计算的只需要按索引查找O(1)，一次循环O(n)下来就能求解。
C.子问题不重叠。
大问题划分成子问题求解。
比如归并排序。
3.没有后效性
原问题的最优解一定会用到子问题的最优解，即原问题的子问题不可能不是最优解。

动态规划问题的两个解决思路：
·Top-down方式
记忆化递归。
·Bottom-up
通常理解意义的DP。