一招团灭动态规划（附所有DP问题汇总）（新手向）

点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝 备战2021秋招面试 微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide

前言

碰到太多的人面试倒在动态规划上了，惋惜之后，毅然写下此文并附上所有的DP问题（和链接）供大家练习用。看完这篇文章，你会发现其实动态规划并没有想象的那么难，不要被它高大上的名字给唬住。只要你够有决心，就算你是新手，动态规划也可以一口气整个给它盘下来。(当然大神都是不用套路，无师自通的，请四十五度角仰望天空保持高冷)

动态规划的理解

开篇第一问，动态规划是什么？动态体现在哪里？又规划了什么？（欸，不对，好像是三问了）

开篇第一答，动态规划问题其实就是 “ 递 归 + 记 忆 化 ” {\color{red}“递归+记忆化”} “递归+记忆化”，这里还不明白这句话没有关系，但是要记着这句话和上面提出的三个问题看下去。

递归我们再熟悉不过了，自己反复调用自己嘛，俗称套娃。比如已经被用烂了但我这里还要再用一次的经典用例——斐波那契数列。防止部分新手没有听过这个数列，我给出其定义： 即定义这样一个数列，前两项值等于序列号，后面每一项是前两项之和，这样就可以通过反复调用自身来求解每一项的值，可以用这样的程序实现：

int Fib(int n)
{
	return n