这是 H1

面试中对动态规划的考查难度不是很难

来源

以斐波那契数列为例，单纯方式的递归会造成指数级的时间复杂度，因为其中有大量重复的计算过程；
因此考虑将重复的数字用数组记录下来–记忆化搜索：自上向下的解决问题
动态规划：自下向上的解决问题

关联

递归问题—重叠子问题+最优子结构（针对最优解问题）—记忆化搜索：自上向下的解决问题
| |
|—动态规划：自下向上的解决问题（可以没有递归过程）

用自上向下的方式去思考，用自下而上的方式去实现。
最优子结构：通过子问题的最优解，可以得到这个问题的最优解

许多实际问题是斐波那契问题：
如爬楼梯，120,64

以343为例：
首先这个问题用暴力搜索方法去思考，由于分割成多少是不知道的，因此不能用循环方式（O（n2）），因此使用递归的方式;
通过画图分析，发现有大量的重叠子问题，因此可以用记忆化搜索来实现。
lc343分别用记忆化搜索和动态规划的思路来实现了。（可以看出，记忆化搜索的方法比较容易想到）
【实际上，这个问题用暴力解法的话：回溯遍历将一个数做分割的所有可能性O(2^N)】

279，91，62

tips：

注意对状态的定义（函数的定义）；【做什么】状态定义不同，则解决方式不同
根据对状态的定义，决定状态的转移，状态转移方程。【怎么做】

198，309这两个问题除了动态规划也可以用其他方法来做

背包问题

时间复杂度：O（NC）
空间复杂度：O（NC）–O(C*2)–O(C)

完全背包问题：每个物品可以无限使用；
多重背包问题：每个物品不止一个，有num（i）个
多维费用：考虑物品的体积和重量两个维度，变成三维数组

背包例子：416，322，377，474，139，494

最长上升子序列问题LIS

注意状态的定义
lc300的两种实现
LIS(i)表示以第i个数字为结尾的最长上升子序列的长度；
LIS(i)表示[0…i]的范围内，选择数字nums[i]可以获得的最长上升子序列的长度。【注意是选择，不是考虑】
lc300的O（n^2）解法；
O(NlogN)解法。链接（新开了数组进行存储有序的序列，并进行二分查找）

动态规划给出具体解

以300LIS为例，给出具体的最长递增子序列，倒着查找
\0-1背包问题,反向重构，需要指出的是，由于反向重构时，需要利用原来的信息，因此对空间优化的方法就不行了

面试算法之动态规划基础