导读｜动态规划问题纷繁复杂，如何系统学习和掌握它？

卢誉声

你好，我是卢誉声。
你是否曾经有过，或者正在经历这样的体验，那就是在学习和掌握了一些数据结构和算法后，面对一个较为复杂的面试题，仍然无从下手？
那个问题看起来好像可以使用递归，但是我该怎么遍历整个数据结构呢？
 
这个问题看起来需要穷举，但排列组合好像挺难的……
 
这里的排列组合情况实在太多了，我到底该怎么优化时间复杂度？
其实，几乎所有人在初学算法和动态规划时都会有这种感受，特别是当待解决的问题步入“穷举”这个不得了的领域时。穷举从来都不是一个好的解决方案，因此针对这类问题的求解方法真是八仙过海、各显神通，我们很难直接从这些解法中找到规律，同时这些解法又晦涩难懂。
正因如此，在面试中如果发现问题需要使用穷举或动态规划，很多人就会变得胆战心惊，无从下手。
但我想告诉你的是，数据结构和算法虽然从表面上看纷繁复杂，但常用的基本思想和方法还真的就不多。这同样适用于动态规划问题，它简直就是模板、套路届的典范。因此，只要我们掌握了正确的学习方法，形成经验式总结，那么当我们再去面对看似“玄幻”的动态规划问题时，就再也不是什么难事了。
所以说，动态规划作为算法面试问题中的一项重要议题，从表面上看似纷繁复杂，但有规可循。今天，我会把自己这些年来总结的学习窍门、遇到的问题和解题思路，进行归纳总结，梳理出一条清晰的路径给你，即如何系统学习和掌握动态规划。我期待这个专栏能让你产生全新的认识，收获清晰的解题思路，轻松跨过大厂算法面试这道坎。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文分享了学习动态规划的方法和技巧，帮助读者系统学习和掌握动态规划。首先，强调建立扎实的基础知识体系，包括掌握基础数据结构和算法，以及锻炼算法编码能力。其次，透彻理解动态规划的基本方法论，包括寻找子问题、递归求解、重叠子问题与无后效性、状态存储等概念。最后，掌握经典问题，总结解题思路，并通过刷题来巩固学习成果。通过本文，读者可以快速了解动态规划学习的基本路径和方法，轻松掌握这一重要的算法思想。文章还强调了总结、分享成为一个习惯，形成正向刺激，并鼓励读者在学习过程中分享经验和思考，让大家一起学习探讨。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(8)

最新
精选

Roger宇
但说实话，自己总结的东西，很多时候感觉并不精妙，刷了一百多道可能就几道题感觉自己的思路无比清晰，总结出来确实还是蛮自豪的。
作者回复: 赞！如果已经能遇到题目且无比清晰，那就说明已经领悟了。绝大多数DP问题都可以通过转化变成经典问题（而经典问题就那么多）。
2020-09-14

8
落曦
学习动态规划之前在网上我看到一位老师是这样讲动态规划的，将问题分成两块状态表示和状态计算状态表示中分成集合（这一类方案存放的是哪一类的值）和属性（值（最大值最小值数量））状态计算当中根据集合列出状态转移方程
作者回复: 恩，可以这样说，只不过我们把状态细化成了“状态”、“状态存储”，把状态转移方程中的“初始状态”提取出来重点标注了。状态其实就是状态表示本身。状态存储就是需要你考虑如何存储状态的解。初始状态就是需要你考虑状态解的边界条件，做特殊处理（这个应该是需要注意的，很多人会忽略其重要性）。
2020-10-19
2
5
Erebus
1.chunked it up; 2.deliberate practice; 3.positive feedback ;
作者回复: 加油学习！Mua
2021-03-25

1
到道可道
先打好基础，后面跟着老师一起开车上路
作者回复: 来，上车！
2022-06-23


Leroy_lamoury
如果不理解算法的思想,不懂得算法的本身,只是靠死记硬背算法题,我觉的走不远的,所以我要从思想抓起,准备学习一番,觉得自己算法不行的原因,觉得子太急于求成,而没有认真的去理解每一道题。到最后遇到一个新题,自己仍然是没有思路的。
作者回复: 记住一个核心，两个基本点。核心是：如果有重复计算，那么想办法用备忘录缓存计算过的结果。基本点：1）先看问题是否涉及穷举 2）再看问题是否满足DP的要求。
2021-10-31


3.141516
总结一下，学习动态规划的方法： 1. 要具备基础的算法和数据结构，如多维数组、树，递归、迭代、回溯，要有一定的编码能力； 2. 掌握基本方法论，就是解题过程和技巧； 3. 自己动手实现掌握经典问题，总结
作者回复: 是的，计算机解决所有问题的基础归根结底是基本的算法和数据结构，没有这些基础就不知道如何建立计算机解决问题的模型，也不知道怎么具体地解决问题。有了基础之后就是学习基本的方法并持之以恒地练习，继续加油哦～
2021-05-10


北顾-岛城
老师声音好好听，冲冲冲！
作者回复: 感谢支持！
2021-03-24


追风筝的人
加油
作者回复: 加油！
2020-10-18



收起评论