原题链接Jump Game II 给定一个数组序列，序列中每一个元素的值表示最多可以向后跳多远，初始时从下标0开始，计算最少跳多少次可以到达末尾的元素位置。
刚开始是想用深度优先（dfs）+ 动态规划解决的，结果竟然超时了，看到答案后真是….哎╮(╯▽╰)╭
对于每个位置，它跳一次可以到达的位置是一个范围，而对于这个范围，跳一次可以到达的位置仍然是一个范围。以示例序列[2,3,1,1,4]为例。 初始时，在下标为0的位置上，可以到达的下标范围是[1,2] 对于下标1，可以到达的下标范围是[2,4]。对于下标2，可以到达的下标范围是[3,4]。所以范围[1,2]可以到达的范围是[3,4]。
所以如果每次移动的都是一个范围，那么直到这个范围包含最后一个位置，就说明已经到达末尾了。而移动的次数，就是移动范围的次数。 代码如下
class Solution { public: int jump(vector<int>& nums) { int n = nums.size(); int steps = 0; /* [start, end]记录当前达到的范围，初始为0 */ int start = 0; int end = 0; while(end < n - 1) { /* 找下次可以到达的最远位置 */ int max_pos = 0; for(int i = start; i <= end; ++i) max_pos = std::max(max_pos, i + nums[i]); /* 对于可以到达最远位置的那个下标i，它可以到达的位置为[i+1, max_pos]，即 * start, ..., i, i+1, i+2, end, ... ,max_pos * 下次的范围就是[end + 1, max_pos] */ start = end + 1; end = max_pos; ++steps; } return steps; } };原题链接 Jump Game 这个就是判断能不能到达最右边，方法和上面一样，转换为广度优先解决 代码如下
class Solution { public: bool canJump(vector<int>& nums) { int left = 0; int right = 0; while(right < nums.size() - 1) { int max_pos = right; for(int i = left; i <= right; ++i) max_pos = std::max(max_pos, nums[i] + i); if(max_pos <= right) return false; left = right; right = max_pos; } return true; } };上面两道题主要是将题目转换为广度优先（bfs）进行解决。因为每个位置可以达到的位置都是一个范围，那么就导致不确定应该将它跳到哪，从而会有很多中可能，深度优先是依次考虑每种可能，会比较慢。而广度优先将所有的可能一起考虑，每次都移动一个范围，从而不需要那么多的迭代（递归）次数。
