要不要准备DP
我的感受是收益率很低。
近期我参加了9家公司的面试，有7家完成VO，剩下两家止步店面，加起来有31道算法面试，其中只有google vo中1题是dp，而且是较简单的dp。
面试dp其实是很好的机会，因为dp题的代码都很好写，基本上状态转移的核心部分代码不会超过10行。所以会有更多时间去解释dp。然后结合画图，也属于较容易把思维说清楚的情况。建议大家把基础的题目的思路多说几遍，然后根据视频里面学到的多画画图，面试会更容易得到认可。
大家自己选择要不要准备dp
我花在DP上的
我看的资料，首先是课堂教学型
- 首先我看的*NOIP的资料，这位老师讲的很好 b站 动规的部分大概从9.62到9.100多
- 然后是MIT open course，youtube
然后是非教学型
- 这个人的youtube channel大家应该在很多地方都能找到推荐，其中也有dp部分 youtube
- C++的专门题解集 github
- 背包九讲，我觉得大家一定要去看看这个，实在是讲得好，很好的背包dp入门教材
- 最后就是 oi 竞赛的部分我没有过多深入，不过简单了解一下还是有帮助的
剩下就是做题
- algo export上做了112题，其中dp 13题。 11%
- leetcode上做了210题，其中dp 65题。 30%
- 总计24%的题目都是dp，并且后期做的leetcode，更偏重dp。
总结
时间上基本上1个月到1个半月花在dp上面。基本做到了常见题型能够解题，简单的变形dp能够比较快转化为基础题型。
NOIP 大家对NOIP可能比较陌生，我稍微介绍一下，NOIP是初中生计算机竞赛，在国内已经办了超过15年了，dp是每年的考题。经过多年的研究，老师们已经可以把基本的dp讲解到初中生都能理解的程度。而且难度并不简单，大家可以自己感受一下。然后也请大家想一个问题，如果大厂对员工的面试中体现的业务能力的要求也就是初中生的学术要求，那么还有什么是你在初中毕业后这么多年读书获得的能够让你超越初中生而被公司录取？
我对dp的一些理解
dp是难的递推。不严谨的通俗来说递推能够继续下去，体现了重叠子问题，而递推能有一个合理的路径，体现了最优子结构。
推的路径
最简单的推的路径就是线性的，其中可以是一个状态推一个状态，也可以是几个状态推一个未来状态。这样的题一般可以表述为从“左推到右”或者从“开始推到结束”。
有时候就算数据变成了图形，其实仍然适用。从“左上推到右下”，仍然可以认为是线性的推广。
树形的推，更多是从小集合推到大集合，有一种合并的感觉，体现在树上就是从叶子往根推。
这里讲的推和树形dp，图形dp等不一定一致。这里是推的方向，也就是状态转移的方向，并不一定等同于数据结构
状态不是一个量，是一组量
我们常用数组表示状态的集合，然后一般数组里面存一个数字，我们就感觉状态其实是一个量，其实不然，状态可以扩展为好几个量。当然你可以最后做成多维数组来写。比如：我们有a，b，c 3个数据来表示一个状态dp[i].a = 1, dp[i].b = true, dp[i] = "hello"也可以写成一个二维的多类型数组dp[i] = [1, true, "hello"]甚至写成三个数组dpa[i] = 1, dpb[i] = true, dpc[i] = "hello" 这个和根据数据结构来想到dp需要二维，在思维上是不一样的
这类题中的经典就是股票买卖
压缩
上面讲了扩展，那么思维上再过度一下就是压缩了。压缩，用通俗的话讲就是不需要了。思维上就是，如果我需要前三个值算第四个值，那么算到第四个的时候第一个值就不用了。所以就可以通过减少存的状态而节省空间了。
更进一步，上面提到的一个状态里面的某些量可能只需要用一次，那我就直接存就好，不需要用数组存了，那么就变成状态之外的量的感觉。这是通过减少存状态的量减少空间。比较经典的题就是最长不下降子序列，其中维护的数组其实是随着状态变而一直在变的，但是没有必要每一次存一个数组（估计也没有会这么干）。
优化
prefix优化 与 单调队列优化
dp中所有的优化里面，我只能理解这一种优化。这种情况多发生在多重循环下，在目前这个循环内需要再做循环来算一些值，一般是最值。而我们可以发现（先是直觉，然后是数学计算）这些最值的计算可能会用到一些相同的量（prefix或是维护一个单调队列或者单调栈），所以可以将内循环的逻辑简化，一般是O（m*m）-> O(m)计算prefix或是其他 + O(m)计算剩下内容。