V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

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

  •  
  •   hakunamatata11 · 2020-04-24 15:45:26 +08:00 · 2028 次点击
    这是一个创建于 1660 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

    丢鸡蛋问题

    有一个 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%的动规题。

    image

    做出动规题,大厂不难进

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

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

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

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

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

    免费试听内容:

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

    免费试听方式

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

    8 条回复    2020-04-26 19:19:19 +08:00
    misaka19000
        1
    misaka19000  
       2020-04-26 18:16:18 +08:00
    图裂了
    mainjzb
        2
    mainjzb  
       2020-04-26 18:22:06 +08:00   ❤️ 1
    一看图片链接。直接简书 copy 过来的
    hakunamatata11
        3
    hakunamatata11  
    OP
       2020-04-26 18:46:03 +08:00
    @mainjzb 因为我是用简书的后台编辑的 哈哈~
    hakunamatata11
        4
    hakunamatata11  
    OP
       2020-04-26 18:46:33 +08:00
    @misaka19000 摊手
    Soar360
        5
    Soar360  
       2020-04-26 18:58:38 +08:00
    李永乐老师讲过这个问题。
    tt67wq
        6
    tt67wq  
       2020-04-26 19:06:28 +08:00 via iPhone
    leetcode 动态规划 结果超时了
    learningman
        7
    learningman  
       2020-04-26 19:18:49 +08:00 via Android
    转移方程推出来就做完了,问题是你推不出来。
    learningman
        8
    learningman  
       2020-04-26 19:19:19 +08:00 via Android   ❤️ 1
    当年高中做不出来的题,放到现在还做不出来。连高中会做的现在都未必会做了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2675 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 03:08 · PVG 11:08 · LAX 19:08 · JFK 22:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.