vlambda博客
学习文章列表

动态规划在初学者看来

似乎是一种高深莫测的算法

每天都会有人发出灵魂呐喊

我太南了！到底该如何搞定动规？

领扣🐱看网上讲动态规划的文章

言必称状态转移方程啦，最优子结构啦

高大上的词一套一套的

对于算法小白来说实在有点劝退

最近逛Quora的时候

看到一个有意思的问题

How should I explain dynamic programming to a 4-year-old?

底下一个获赞50K的回答是这样的

看完之后是不是豁然开朗？

我们都知道

动态规划是把一个大问题拆解成一堆小问题

但这并不能体现动规的核心思想

或者说

一个问题之所以能用动规解决

并不是因为它能拆解成一堆小问题

能不能用动态规划

取决于这些“小问题”会不会被重复调用

顺着这个思路 

这样我们就能总结出

可以使用动规的问题都遵循一些特点

比如提问方式一般是

1. 计数

有多少种方式走到右下角

有多少种方法选出K个数使得和是Sum

2. 求最大最小值

从左上角到右小角路径的最大数字和

最长上升子序列长度

3. 求存在性

取石子游戏，先手是否必胜

能不能选出K个数字使得和是Sum

恰好就是判断是否需要用动态规划

接下来的解题

我们可以用一套完整且通用的解题思路

4.问题要求的最后答案是什么

如果你还想进一步搞懂状态转移方程怎么找

解决更多类型的动态规划题

对动态规划算法进行时间和空间上的优化

只需要来上《动态规划专题班》

7节课帮你搞定99%的动规题！

上完这门课，你可以做到

1. 迅速判断面试常见动规题并找到解题要领

2. 遇到动态规划变种题也能轻松解决

3. 对动态规划算法进行时间和空间上的优化 

4. 面试中将不再有你不会做的动态规划题

谁来讲

侯卫东  FLAG工程师

清华大学毕业，全国算法竞赛金牌得主，参加过ACM国际大学生程序设计竞赛全球总决赛。斩获 Google，Facebook，Microsoft，Uber， Dropbox 等多家offer，拥有丰富的面试和面试官经验。

不知道课程是否适合你？

不知道老师讲得到底好不好？

来免费试听就知道啦！

免费试听内容

动态规划的解题要领

动态规划三大类

求最值/计数/可行性

常见动态规划类型总结

免费试听方式

互动课形式：随时报名，随时听课

长按二维码报名免费试听

或者点击 阅读原文

点下“在看”，秒懂动规