谷歌的这道经典题，为何成为面试者绕不开的“噩梦”

[hakunamatata11]

动态规划在初学者看来似乎是一种高深莫测的算法。刷一道动规题，想必同学们都有这样的体验：

可以用动规，但没（想）有（不）必（出）要（来），暴力解之……然后一看答案，为什么这么简单？怎么想到这种解法的？

于是动规就成了很多人求职路上的“拦路虎”和绕不开的“噩梦”。

题型众多，如何判断动规题

来看一道谷歌面试中的经典动规题。

丢鸡蛋问题

有一个 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 步解题思路：

• 1.确定状态是什么
• 2.状态转移方程是什么
• 3.状态的初始值是什么
• 4.问题要求的最后答案是什么

按照这套思路一步一步走下去，基本可以搞定 99%的动规题。

做出动规题，大厂不难进

曾经就有学员因为上过《动态规划专题班》，电面一眼便看出是 DP，快速秒掉后，follow up 也是老师课上讲的空间复杂度优化，等待两周后顺利收到了 onsite 。

《动态规划专题班》讲解了所有的动态规划考题类型，follow up 常考的动态规划时间空间优化、打印路径等也都有所涉及，只需 7 节课，帮你搞定大厂动态规划题。

戳我免费报名试听，你就可以:

1. 对于面试中常见动态规划题目能迅速判断并找到解题要领
2. 对于动态规划变种题能找到解题的突破口并轻松解决
3. 可以对动态规划算法进行时间和空间上的优化
4. 面试中将不再有你不会做的动态规划题

不知道课程是否适合你？不知道老师讲得到底好不好？来免费试听就知道啦！**

免费试听内容:

动态规划的解题要领 动态规划三大类 求最值 /计数 /可行性 常见动态规划类型总结

免费试听方式

互动课形式：随时报名，随时听课：https://www.jiuzhang.com/course/36/?utm_source=sc-v2ex-fks

[misaka19000]

图裂了

[mainjzb]

一看图片链接。直接简书 copy 过来的

[hakunamatata11]

@mainjzb 因为我是用简书的后台编辑的 哈哈~

[hakunamatata11]

@misaka19000 摊手

[Soar360]

李永乐老师讲过这个问题。

[tt67wq]

leetcode 动态规划 结果超时了

[learningman]

转移方程推出来就做完了，问题是你推不出来。

[learningman]

当年高中做不出来的题，放到现在还做不出来。连高中会做的现在都未必会做了。