动态规划在初学者看来似乎是一种高深莫测的算法。刷一道动规题,想必同学们都有这样的体验:
可以用动规,但没(想)有(不)必(出)要(来),暴力解之……然后一看答案,为什么这么简单?怎么想到这种解法的?
于是动规就成了很多人求职路上的“拦路虎”和绕不开的“噩梦”。
来看一道谷歌面试中的经典动规题。
丢鸡蛋问题
有一个 n 层的建筑。如果一个鸡蛋从第 k 层及以上落下,它会碎掉。如果从低于这一层的任意层落下,都不会碎。
现有 m 个鸡蛋,用最坏的情况下实验次数最少的方法去找到 k, 返回最坏情况下所需的实验次数。
LintCode 链接: https://www.lintcode.com/problem/drop-eggs-ii/description
这道题光是理解题意就难倒了很多同学,什么叫“最坏”情况?什么又叫实验次数“最少”?
这也是动规题的第一个难点,因为动规适用题型众多,又没有固定模板。所以解决动态规划问题,首先要判断是否需要用到动态规划。
可以使用动态规划的问题一般都遵循一些特点,比如提问的方式一般是:
1. 计数
有多少种方式走到右下角有多少种方法选出 K 个数使得和是 Sum
2. 求最大最小值
从左上角到右小角路径的最大数字和最长上升子序列长度
3. 求存在性
取石子游戏,先手是否必胜能不能选出 K 个数字使得和是 Sum 所以对于这类最优解问题,往往可以先尝试动态规划的方法。这就需要我们首先找到构成最优问题的最优子问题,然后确定状态转移方程,问题便迎刃而解了。
4 步轻松搞定 99%的动规题
然而对于初学者来说,DP 状态、状态转移方程这些概念又让人摸不着头脑,很多同学纷纷弃坑。
其实任何算法的学习都有它的规律和套路,只要掌握好出题规律和解题套路,再加上大量的刷题练习,搞定动规并不是什么难事。
就像侯卫东老师在《动态规划专题班》总结的动规4 步解题思路:
按照这套思路一步一步走下去,基本可以搞定 99%的动规题。
曾经就有学员因为上过《动态规划专题班》,电面一眼便看出是 DP,快速秒掉后,follow up 也是老师课上讲的空间复杂度优化,等待两周后顺利收到了 onsite 。
《动态规划专题班》讲解了所有的动态规划考题类型,follow up 常考的动态规划时间空间优化、打印路径等也都有所涉及,只需 7 节课,帮你搞定大厂动态规划题。
戳我免费报名试听,你就可以:
不知道课程是否适合你?不知道老师讲得到底好不好?来免费试听就知道啦!**
免费试听内容:
动态规划的解题要领 动态规划三大类 求最值 /计数 /可行性 常见动态规划类型总结
免费试听方式
互动课形式:随时报名,随时听课:https://www.jiuzhang.com/course/36/?utm_source=sc-v2ex-fks
1
misaka19000 2020-04-26 18:16:18 +08:00
图裂了
|
2
mainjzb 2020-04-26 18:22:06 +08:00 1
|
3
hakunamatata11 OP @mainjzb 因为我是用简书的后台编辑的 哈哈~
|
4
hakunamatata11 OP @misaka19000 摊手
|
5
Soar360 2020-04-26 18:58:38 +08:00
李永乐老师讲过这个问题。
|
6
tt67wq 2020-04-26 19:06:28 +08:00 via iPhone
leetcode 动态规划 结果超时了
|
7
learningman 2020-04-26 19:18:49 +08:00 via Android
转移方程推出来就做完了,问题是你推不出来。
|
8
learningman 2020-04-26 19:19:19 +08:00 via Android 1
当年高中做不出来的题,放到现在还做不出来。连高中会做的现在都未必会做了。
|