边界条件|如何快速从算法萌新逆袭成为码神？( 二 ) 算法萌新在刷力扣时

文章插图
通过以上两个题，相信你对二分法已经有了一个基本认识，他们都有一个共同点：答案是有界且单调的。事实上，只要是满足此条件的题目都可以使用二分法解决。所以我们分析题目时，可以通过检查这一条件来判断是否是二分算法的题目。
接下来我们再来分析一下动态规划题目的特点，选择“动态规划”标签：
文章插图
粗略浏览，可以发现，题目中很多带有“最大/最小”、“最长/最短”、“不同”字样。上文已经说到，简单的题目往往更典型，我们以一道简单题目为例：
70. 爬楼梯力扣
这是一道典型的动态规划题目。分析题目：假如我们要到达第 100 步台阶。我们不可能一步登天，直接飞上去。我们只能从第 98 步走两步到达，或者从 99 步走一步到达。
同样，我们也不可能直接飞到 98 步，我们只能从 96 步走两步到达，或者从 97 步走一步到达。
如果用 f(n) 表示到达第 n 步的走法，根据我们的分析，以下方程成立：
f(n) = f(n-2) + f(n-1)
【边界条件|如何快速从算法萌新逆袭成为码神？】边界条件如下：
f(1) = 1
f(2) = 2
所以我们可以写出以下算法：
文章插图
然而这样是不能通过的，因为递归会带来大量的重复计算，所以我们将其修改为迭代：
文章插图
这样写这道题目就 AC 了。这道题很好的体现了动态规划算法题目的特点：问题能够以大化小，化到最小时有边界条件。
对于动态规划题目，我们只需要处理以大化小的过程和边界条件即可。这个以大化小的过程，专业术语叫”状态转移“ 。状态转移的条件被称作“状态转移方程” ，本题中，状态转移方程就是：f(n) = f(n-2) + f(n-1) 。只要找出了”状态转移方程” ，就可以很轻松的解决动态规划问题，这就是动态规划算法的套路。
此题还可以再次优化，仔细分析题目可知，我们并不需要记录 f(i) 的每一个值，只需要记录前两个值即可。也就是只记录到达前一步阶梯的方法总数和到达前两步阶梯的方法总数，进一步优化的算法如下：
文章插图
对于每一个题目，不要仅仅满足于通过。最好是不断地优化代码，使得其时间复杂度和空间复杂度最低。养成这个好习惯，以后一出手就是最优方案，有助于我们的编程水平进一步提升。
文章插图
总结刚开始刷题时，遇见不会的题目是很正常的。不必焦虑，可以先从不需要算法的 Easy 题入手，按照本文所讲的先写伪代码，再逐步补全的方式编程，可以让你少走很多弯路。此外，还可以去力扣题解区看看别的小伙伴的解题思路，开拓解题思维。
做算法题时循序渐进，不要上来就做困难题目， Easy 题反而更加典型，不掺杂其他算法在其中，更有助于萌新理解此类算法。每个题目多刷几遍，不断地优化代码，直到脑中对此题有一个清晰的认识，切忌“萌混过关” 。
学习算法要渐次进行，先掌握一类算法，钻研透了再去掌握另一类。俗话说“贪多嚼不烂” ，改编王健林的话说就是：“年轻人想成为掌握所有算法的大牛这是对的，但建议先定一个能达到的小目标，比方说我先掌握一个算法。 ”
一把利剑胜过一张薄饼。
本文作者：Alpinist Wang
声明：本文归 “力扣” 版权所有，如需转载请联系。