腾讯面试题：青蛙跳跳跳

01

青蛙的故事

青蛙公主是远近闻名的大美蛙🐸，她一心想找一个聪明的老公，于是设下擂台，比武招亲：有连续的木板，因为材质不同，每个木板能跳的最大距离有限，来应招的青年才俊，需要判断，是否能跳到最后一块板子。

让我们来看看输入参数：一个非负整数数组，青蛙位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。输出就更简单：能否跳到。

02

解题思路

按照一般的解题思维，DFS肯定可以做，但效率应该不是最高。递推的话，动态规划可以考虑，同时看看有没有使用贪心算法的可能性，如果能贪心，那可能就是最简路径。

很幸运，这道题无论是DFS，还是动态规划，亦或是贪心算法都可以做，我比较喜欢这类题，从不同思路，开展不同做法，互相比较，归纳复盘，容易得到提高。话不多说，我们来逐个看看。

03

花式吊打

DFS深度优先算法

最直接的解法，就是基于每种可能，即每块板子可能的跳跃距离，进行DFS递归搜索。这种算法思路比较无脑，缺点显而易见：时间复杂度很高，大概率会超时。

换个角度：目标是最后一个木板。那么往前找到所有能跳到目标的木板，然后以这些木板为目标，递归查找下去。这种算法速率也一般，算是优化版的DFS。

果不其然，运行超时，蛙蛙流泪。

动态规划

我们定义一个数组dp，dp[i]表示当前可以覆盖的最大范围。当前位置能否可达很简单，判断dp[i-1]是否小于i，如果小于就不可达。如果可达，更新dp[i] = Max(dp[i-1], i+nums[i])。

由上图执行结果可以看到，按照动态规划执行的数据，相比DFS是飞跃，耗时减少2/3，内存消耗减少100%以上，时间复杂度应该已经是最优，后面就看空间上是否可以优化。

贪心算法

贪心算法，顾名思义，就是足够贪心。如果当前木板能跳到的距离比当前能达的距离更远，就跳到当前木板，否则就先停留在当前木板。按照这样的规则，一直跳到最后一块板，其间永远站在能跳的最远的木板。如果中间有位置不可达了，那就是跳不到，因为在贪心的基础上，当前点已经是覆盖范围最大的了，如果这样都跳不到，其他方式也不行的。

我们能看到这样写代码，简洁优雅，耗时满足预期，写完给自己点个赞👍，青蛙王子也得感谢我！

但是仔细想想，上面的代码其实可以更简洁明了。因为在本题中跳点不是必要项，换句话说，我们可以从关注跳点，变成关注距离。优化后的代码如下，是不是更加清晰？

把简单的事情做复杂不算什么。把复杂的事情越做越简单，才是能力提升的关键！

逆推法

实不相瞒，这题做到这里，还做出感觉了。我就想，还有没有其他解决方法？

换个角度思考一下，之前大多为正向推导，但是DFS是逆向行走，说明逆推是可行的，只是我们嫌弃DFS效率太低。

对于一个目标位置，我们往前找能跳到该位置的最近的木板，将这个木板作为我们新的目标。这样持续倒推，如果最终推导到了第一块木板，也就是我们的起点，那么就证明可以从起点跳到终点。

注意，我们来仔细思考下这种方式和DFS的不同，DFS是基于当前位置，从后往前递归所有能跳到当前木板的情况，会走完多条分支路径；而这种逆推方式，只会随遇而安地往前挪挪，是O(n)的复杂度。

04

蛙蛙复盘

横看成岭侧成峰，条条大路通罗马，一个简单的跳板运动，居然有这么多思维方式。把一件事情做到极致，我们也一定会收获多多。做算法题，不仅要尝试beats 100%，更进一步的追求是将各种方式都做透彻，每种方式可能有自己的优缺点，很可能加一个限制条件，当前最优解就成死路了。

当然，最重要的是，这样的做题习惯训练了我们不同思维方式。无论是在学习还是工作中，一个问题，你能给出好几种解决方案，还不能成为这条街上最靓的仔？