跳跃游戏类题目 总结篇

一.跳跃游戏类题目简单介绍

        跳跃游戏是一种典型的算法题目，经常是给定一数组arr，从数组的某一位置i出发，根据一定的跳跃规则，比如从i位置能跳arr[i]步，或者小于arr[i]步，或者固定步数，直到到达某一位置，可能是数组的最后一个位置，也有可能是某一特别的数值处，也有可能在这个过程中，可能需要求解可能存在的最大值或者最小值。

        对于跳跃游戏类的题目，经常使用贪心、动态规划、dfs、bfs等方法解决，对于可以使用dfs解决的题目，经常也可以使用动态规划，但一般贪心可以有更好的时间复杂度和空间复杂度。还有经常使用的动态规划剪枝、前缀和、滑动窗口和BFS，由于在大部分情况下，能用DFS解决的题目都可以用BFS解决，且两种方法有基本相同的复杂度，尤其是在跳跃游戏这类题目中，可以视为一种方法。

二.跳跃游戏类经典题目

        在leetcode上有关于跳跃游戏类的题目主要分为两大类，一个就是跳跃游戏，另外一个是跳跃游戏的衍生，比如青蛙酱和跳骚，又或者是其他小动物，比较经典的题目有：

（1）leetcode70 爬楼梯
（2）leetcode剑指 Offer 10- II. 青蛙跳台阶问题
（3）剑指 Offer II 088. 爬楼梯的最少成本
（4） leetcode55 跳跃游戏
（5）leetcode45 跳跃游戏 II
（6） leetcode1306 跳跃游戏 III
（7）leetcode1696 跳跃游戏 VI
（8）leetcode1871 跳跃游戏 VII
（9）leetcode1413 逐步求和得到正数的最小值
（10）leetcode 403 青蛙过河

        以上题目都在前三篇中出现过，具体的题解不再赘述，可参考：

跳跃游戏 （贪心/动态规划/dfs）_跳跃游戏动态规划_ForwardSummer的博客-CSDN博客

跳跃游戏 （动态规划剪枝/前缀和/滑动窗口/BFS剪枝）_ForwardSummer的博客-CSDN博客 

跳跃游戏 （DFS-＞记忆化搜索-＞动态规划/贪心证明）_ForwardSummer的博客-CSDN博客 

那么还有一些其他的跳跃游戏类的题目，可以进行尝试：

（1）LCP 09 最小跳跃次数
（2）1345 跳跃游戏 IV
（3）1340 跳跃游戏 V
（4）1654 到家的最少跳跃次数
（5）975 奇偶跳

三.跳跃游戏类题目 解题方法与技巧

        在整体上，跳跃游戏的题目基本都可以使用DFS解决，如果在时间复杂度上不能满足要求，那么加上一个记忆化搜索基本可以解决大部分的题目，另外还可以进行剪枝，在DFS和BFS和动态规划时也经常使用。对于有些题目，动态规划反而要比DFS、BFS的方法好理解，当明白状态的转移后，不用再去具体怎么走，边界条件如何，反而更容易。

        对于可以使用动态规划解决的题目，都可以使用DFS来做，如果在刚开始不能够很好的推出状态方程，不像  leetcode70 爬楼梯  这种可以一眼看出状态转移规律的，还是建议先写DFS，明确边界条件，列举所有可能下一次走的可能路径，进行递归，注意不要StackOverFlow，基本都可以解决问题，最多加上剪枝和记忆化搜索。对动规三部曲不熟悉，可以看看之前的文章，以及左神老师的视频，在动态规划推导方程这块讲的还是很不错的。

跳跃游戏 （DFS-＞记忆化搜索-＞动态规划/贪心证明）_ForwardSummer的博客-CSDN博客

Java-算法-动态规划_java动态规划_ForwardSummer的博客-CSDN博客 

【一周刷爆LeetCode，算法大神左神（左程云）】

        对于有些题目，可以使用贪心的思想，但此类题目往往不好想，且难以证明贪心的正确性，需要对题目的敏锐感觉以及大胆的尝试和边界的判断的准确性。

四.跳跃游戏类题目 做题顺序推荐

        对于在前三篇的文章已经做过的十道题目，接下来做一个顺序推荐。

（1）leetcode70 爬楼梯（动态规划，滚动数组优化）

（2）leetcode剑指 Offer 10- II. 青蛙跳台阶问题（动态规划，整数取值较大的取余操作）

（3）剑指 Offer II 088. 爬楼梯的最少成本（动态规划，开始出现成本项） 

（4）leetcode55 跳跃游戏（模拟，贪心）

（5）leetcode45 跳跃游戏 II（动态规划，动态规划剪枝，贪心）

（6）leetcode1306 跳跃游戏 III（DFS）

（7）leetcode1696 跳跃游戏 VI（动态规划，动态规划剪枝，动态规划+滑动窗口）

（8）leetcode1413 逐步求和得到正数的最小值（动态规划，滚动数组）

（9）leetcode1871 跳跃游戏 VII（动态规划，动态规划+前缀和，动态规划+滑动窗口，BFS剪枝）

（10）leetcode 403. 青蛙过河（DFS，记忆化搜索，动态规划）

以及其他五题：

（11）1654 到家的最少跳跃次数

（12）975 奇偶跳

（13）1340 跳跃游戏 V

（14）1345 跳跃游戏 IV

（15） LCP 09 最小跳跃次数