狗家面试太难！coin change等动规题及多串找公共子串解析

[id_424845016]id_70345540]

有多个字符串要找公共子串，这种情况下至少需要用到后缀数组，并且我不确定height能否在线性时间内完成。

福利预览

讲座《动态规划入门和面试真题讲解》

领取方式见文末

最近参加谷歌面试的同学，纷纷反馈，谷歌考查动态规划时，难度不断增加，几乎所有人面对动态规划，都不知如何应对 。

做出1道动规题，当场拿offer

事实上，近年来各大厂都把动态规划纳入了面试。不止谷歌是这样，因为动态规划不像递归等题目，无法通过背诵程序来解决。它的题型十分丰富，并且每种题型都有足够的难度。关键在于，它还没有那么“难出天际”！

出一道动态规划题，比做好几道算法题更能有效测试面试者的水平，做出一道动态规划题，基本上就等于赢得了面试官的认可！

让我们来看看，这道当场让面试官给offer的题是怎么样：

题目：数字三角形

给定一个数字三角形

找到从顶部到底部的最小路径和

每一步可以移动到下面一行的相邻数字上

LintCode答案

>>>>

样例1

输入下列数字三角形：
[
?????[2],
????[3,4],
???[6,5,7],
??[4,1,8,3]
]
输出：11
解释：从顶部到底部的最小路径和是11，具体为2加3加5加1等于11 。

>>>>

样例2

[
?????[2],
????[3,2],
???[6,5,7],
??[4,4,8,1]
]
输出：12
解释：从顶部到底部的最小路径和是12 ，其计算方式为2 + 2 + 7 + 1 = 12 。

动规题难？这些步骤你做了吗？

Step1：判断题

不知道你是否看出来，解出动态规划存在一个前提，那就是必须判断出这是不是一道动态规划题。动态规划是一种算法，它通过“大而化小”的思路来解决问题。

如果这道题有以下任意特点：

1. 求最大值/最小值

2. 求可不可行

3. 求方案总数

那么这道题有90%的概率，需要用动态规划来求解。相反地，如果一个问题要你求出全部的方案和结果，那就肯定不是用动态规划来解决。

Step2：选择题

判断好之后，能够对这道题开展分类，寻找到对应的类别以及相似的问题。

动态规划题目类型：

矩阵型、序列型、双序列型、划分型

区间型、背包型、状态压缩型、树型

Step3：解答题

接着从下面的4个要素去逐步剖析解决这道题：

动态规划解题4步骤：

1. 状态是什么

2. 状态转移方程是什么

3. 状态的初始值是什么

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

当你完成对每个步骤的分析，此时，整道动态规划的问题就基本得到了解决。

要是想通过实际操作来检验自身动态规划能力，那就可以前往LintCode刷题，这里有80多道动态规划练习题：

这些是从实际面试问题里汇总而来的精选练习，熟练掌握这些练习题，基本上就能满足面试需求。

学动态规划最快的办法？

如今正处于秋招阶段，要是你还没有彻底弄明白dp问题，那肯定需要专业老师为你答疑解惑。

九章最近有一门很火爆的课程叫《动态规划专题班》，它依据最新面经，总结出了一套完整的动态规划解题思路，通过7节课能够帮你搞定动态规划面试题。

谁来讲

FLAG工程师

毕业于清华大学，是全国算法竞赛金牌获得者，参加过ACM国际大学生程序设计竞赛全球总决赛，获得了Google、Facebook、Microsoft、Uber、Dropbox等多家公司的录用通知，具备丰富的面试经验以及作为面试官的经验。

课程亮点

课程大纲

动态规划入门

动态规划初探+坐标型动态规划+位操作型动态规划

序列型动态规划

划分型，博弈型和背包型动态规划

背包动态规划和区间型动态规划

双序列动态规划

动态规划难题专场

不知道课程是否适合你？

不知道老师讲得到底好不好？来试听就知道啦！

课程报名方式

长按二维码免费报名试听