通过简单的 “刷题” 就能搞定算法笔试题吗？

刷过Leetcode的都知道，每道题的解法可能不止一种，其中不乏让我们望尘莫及的。不过，这些解法花些时间，我们也能看懂，但是我们常常感叹，我们当初怎么就想不到呢！

不知道大家有没有这种感觉？

如果我们拿到一道题目，习惯用写业务逻辑的思路，从开始到结尾按部就班地构思，这种效果好吗？恐怕不太可取！

这样做就真成了刷题了，效果可能不明显。我们做题应该是为了培养思维，在面试时迅速想出高效的实现思路。至于编码，只要平时加以训练，反而应该不是问题。

关注本公众号的会有一些ACM大神，他们强于常人的缘由即在于能很快想出常人短时间难以想到的优秀解法。接下来，以靠近这些大神为目标，和大家一直专注于面试算法题的分析思路、算法思想，以及如何快速在脑海里形成算法伪代码。至于之后的求解代码我放在次要位置，甚至忽略，因为有了算法思路，这些可能就不是重点。

今天，先热身以下。说说动态规划，实话说，dp真的是非常灵活的算法思想，最重要的是找到状态迭代公式，然而这往往是比较有难度的，如果没有有目的的多训练，可能难以在短时间内快速找到状态转化方程。

dp最经典和入门级的例子还是爬楼梯。

每一次你面临两种选择，爬一层，或爬两层，爬到n层一共有多少种方法。 我们面临的第一个疑问：它可以用动态规划吗？ 要回答这个问题，可以参考算法导论上给出的两个前提。

通俗地说，假如知道了爬到第i层的所有方法为f(i)，0<=i <= n-1 ，那么爬到第i-2层和i-1层的所有方法为： f(i-2)， f(i-1) ，此时 i>=2 , 并且爬到第i层后，一定是从第i-2层或第i-1层过来的，则

1f(i) = f(i-2) + f(i-1) ，2<=i<=n
2

这个公式就是状态转移方程，同时它也表明爬到第i层的所有方法，这个子问题的最优解，与整个问题的最优解是一致的。

有了这个迭代公式，自然可以求出爬到任意楼层的所有方法。

根据这个题目，可以有很多变种，比如：

起始位置在第一层，交付这一层的费用后，可以选择向上爬一层或两层，问爬到顶层的最低成本。举个例子，已知 cost[5] = {1,4,5,3,1}，则最节省成本的走法为：1 + 5 + 1= 7

如何构思这道题，不难发现，整个问题的最优解和子问题的最优解是一致的，故设爬到第i层的最小成本为f(i)，i层的子问题的子问题是爬到第i-2层或第i-1层，如果爬到第i-2层后，支付此楼层费用后，爬两层后可以到第i层，故：

1f(i) = f(i-2) + cost[i-2] 2<=i

同理，从第i-1层过来的费用为:

1f(i) = f(i-1) + cost[i-1] 1<=i

所以，爬到第i层的最低成本即为：

1f(i) = min(f(i-2) + cost[i-2], f(i-1) + cost[i-1] ) 2<=i
2f(0) = 0
3f(1) = cost[0]
4

根据以上迭代公式可以求出爬到任意楼层的的最小成本，爬到第n层的时间复杂度为O(n)

再观察上面的迭代公式，cost[n-1]好像没有遍历到，因为i的最大值为n-1，故等式右侧cost只能取值到cost[n-3]和cost[n-2]

这是一个算法的重要细节，需要考虑！函数的自变量的取值区间需要考虑。

如何解决这个算法的边界呢？最简单的方法使用哨兵sentinel，可以在cost的最后添加一个元素0，确保遍历所有楼层。

当然，还有一些变种，比如在f(0), f(1) 这些边界值上做文章。比如Leetcode的有道题就是这样做的：起始位置可以在第1层或第2层，所以：

1f(1) = 0 //爬到第2层的成本变为0

其他与上面分析完全一致

算法的灵活性就和算法题的灵活性一样，改变一个细微的条件后，就需要考虑对整个算法的影响，有时甚至一个微小的变化，就会导致整个算法重新设计。

所以，算法工程师面临的压力是很大的，需求的一点变化，动辄就要修改整个算法。另一个角度来说，编写算法框架的难度就不言而喻。

要知道学会分析算法题不是一朝一夕的。那么是不是可以跨过这一步呢？

Impossible!

或许刚开始这有些繁琐，耽误时间，但是当它成为你的唯一选择时，它何尝又不是捷径呢？

记得卡内基梅隆cs系最受欢迎的教授prof Kosbie说过，“曾有些学生问我，在CMU怎样才能拿到一个好的分数”，他告诉学生完成每次作业前的材料学习，学生们说为了完成作业要去读这么多书，我们没有时间。他说 “或许这很花费时间，但是这样做可以帮助你深入理解这门课并获得理想的分数，同时为你以后的职业生涯打好根基，并告诉学生：If you don't have time to do that , you don't have time not to do that. ”

引人深思