2w+字绝杀!动态规划.pdf来了

前言

大家好，我是bigsai，好久不见，甚是想念。

今天给大家分享我的动态规划原创的pdf，2w多字，里面囊括28道最经典的动态规划问题，可谓是绝杀利器(自吹一波)！

一直有朋友说动态规划很难，确实动态规划非常灵活，但是对于找工作来说，我们需要掌握的动态规划其实相比竞赛范畴那些复杂的没那么难，一些状态转移方程、数组定义方式有的还是很容易看出来的，有的不容易看出来思考看别人解答也是可以理解的。

刚好现在牛客的一个专栏笔刷101有动态规划系列的题，我把里面和自己加了一些动态规划的题目都写了，我的实现是基于牛客的笔刷101基础，但我给了牛客和力扣的对应链接的。

牛客笔刷101链接：https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

这个题库总结不错，建议大家刷一下。

什么是动态规划

动态规划的范围虽然确实是很广很难，但是从整个动态规划出现的频率来看，这几种基础的动态规划理解容易，学习起来压力不大，并且出现频率非常高。

这几个常见的动态规划有：连续子数组最大和，子数组的最大乘积，最长递增子序列(LIS)，最长公共子序列(LCS)，最长公共子串，最长公共子串，不同子序列。

首先很多人问，何为动态规划？动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。通俗一点动态规划就是从下往上(从前向后)阶梯型求解数值。

那么动态规划和递归有什么区别和联系？

总的来说动态规划从前向后，递归从后向前，两者策略不同，并且一般动态规划效率高于递归。

不过都要考虑初始状态，上下层数据之间的联系。很多时候用动态规划能解决的问题，用递归也能解决不过很多时候效率不高可能会用到记忆化搜索。

对于一个动态规划的问题来说，通常解决也是有技巧的，大致来说有以下几个步骤：

• 确定dp数组含义：定义dp数组的维度以及dp数组定义(对应下标值的含义)。

• 确定递推式：确定当前下标的dp值与前面已确定结果之间的关联。

• 初始化dp数组：考虑dp数组的0号位置、边缘位置以及特殊情况的一些值。

• 确定遍历顺序：正确的遍历进行dp推导，保证让数据结果一层一层"铺满"。

当然动态规划也能有很多空间优化，有些只用一次的值，你可以用一些变量去替代。有些二维数组很大也可以用一维数组交替替代。当然动态规划专题很大，有很多比如树形dp、状压dp、背包问题等等经常出现在竞赛中，能力有限这里就将一些出现笔试高频的动态规划！

最后做动态规划的问题时候，有几个小建议一定要处理好：

• 多尝试dp数组维度和含义，这个需要有一定的经验才更好。

• 初始、边缘等情况初始情况好好考虑，要让初始、边缘等能够正常参与递推。

• 推导状态转移时候要跳出思维限定，只寻找这个结果和前面的联系(不要考虑前面哪里来的、前面值是否正确之类)，这点和有递归信赖是有点类似的。

不太明白?看完这些题解你应该会明白：

结语

这个其实还没有完全完善(在dp系列还没有做好归纳总结，缺一些)，但是鉴于很多人需要，我就先分享给大家了，暂时先不放在公众号分享给大家(后面完善再放到公众号)，有些不错的经典题后面也会单独作为文章发出来分享交流。

后续都会同步到仓库中，还求个star：https://github.com/javasmall/bigsai-algorithm

获取方式：

• 分享在交流群中，有我好友的可以直接问我要，可以分享给好友

• 加我好友(bigsai66)备注(动态规划)我发给你。

因为整理比较粗糙，难免可能有些差错，先分享给一部分人看看，有问题修修改改然后不断完善，最近有点忙无法保证输出，咱们后面再见！

欢迎添加 「bigsai66」，备注[动态规划]

好东西记得分享(点赞、再看)一下