Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
上一题是问能否跳到数组右边，本题问最少需要多少跳能跳到数组右边，第一反应是DP。
设dp[i]表示从位置i跳到数组右边最少需要的跳数，则dp[n-1]=0，dp[0]就是最终结果。此时我们需要从数组右边往左边遍历，假设dp[i+1,…,n-1]都求出来了，现在要求dp[i]。站在位置i，我们最远能跳到i+A[i]，所以我们就看看从i跳到哪个$j\in[i,i+A[i]]$能获得最少的跳数，从i跳到j需要增加一跳，所以递推式就是$dp[i]=min\{dp[j]+1\},\quad j\in[i+1,i+A[i]]$
这种思路的代码如下：
class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
if (n <= 1)
return 0;
int maxJump = n – 1;
vector<int> dp(n, 0);
for (int i = n – 2; i >= 0; –i) {
int curMinJump = maxJump;
for (int j = i + 1; j <= nums[i] + i && j < n; ++j) {
curMinJump = min(curMinJump, dp[j] + 1);
}
dp[i] = curMinJump;
}
return dp[0];
}
};可惜，本代码提交TLE，在最后一个大数据集上超时了。但是我还是觉得DP方法是一个基本法，而且如果要求出最小跳的路径，也很方便，如下代码，打印的时候，从pre[n-1]不断找前驱位置就好。
class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
if (n <= 1)
return 0;
int maxJump = n – 1;
vector<int> dp(n, 0), pre(n, 0);
for (int i = n – 2; i >= 0; –i) {
int curMinJump = maxJump, k = 0;
for (int j = i + 1; j <= nums[i] + i && j < n; ++j) {
if (dp[j] + 1 < curMinJump) {
curMinJump = dp[j] + 1;
k = j;
}
}
dp[i] = curMinJump;
pre[k] = i; // 从i跳到k能获得最小跳数
}
return dp[0];
}
};讨论区看到一个O(n)的解法，很厉害。思路和上一题LeetCode Jump Game很类似，依旧维护一个当前能跳到的最远位置curFarthest，同时维护一个当前跳能跳到的范围[curBegin, curEnd]，一旦i超过了curEnd，说明应该开启下一跳了，同时更新curFarthest。
这种算法的思路很巧妙，他不管你当前跳到底跳到哪里，只管你能够跳到的范围，一旦走出这个范围，就必须开启下一跳了。代码如下：
class Solution {
public:
int jump(vector<int>& nums)
{
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < nums.size() – 1; ++i) {
curFarthest = max(curFarthest, i + nums[i]);
if (i == curEnd) {
curEnd = curFarthest;
++jumps;
if (curEnd >= nums.size() – 1)
break;
}
}
return jumps;
}
};本代码提交AC，用时22MS。第10行是增加的提前结束的代码。
参考：
- http://blog.unieagle.net/2012/09/29/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Ajump-game-ii%EF%BC%8C%E4%B8%80%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
- https://discuss.leetcode.com/topic/28470/concise-o-n-one-loop-java-solution-based-on-greedy
- http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
二刷。这题很有意思，时隔三年再刷此题，依然不会。首先想到的依然是DP的解法，不过这个DP比以前写的DP好理解一些，代码如下。思想就是steps[i]保存了要跳到i位置最小的步数，则初始时steps[0]=0，其他位置都是无穷大。然后，对于每个位置i，更新它能跳到的所有target位置的最小步数。最后返回steps[n-1]。
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> steps(n, INT_MAX);
steps[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= nums[i]; ++j) {
int target = i + j;
if (target < n) {
steps[target] = min(steps[target], steps[i] + 1);
}
else {
break;
}
}
}
return steps[n - 1];
}
};同样，DP解法在最后一个样例上TLE了。
评论区看到另一个O(n)的解法，比之前的更好理解： https://leetcode.com/problems/jump-game-ii/discuss/18028/O(n)-BFS-solution。这个解法把该问题想象为一个BFS层次遍历的问题。
以输入样例s=[2,3,1,1,4]为例，最开始我们在起点s[0]，它最多能跳2步，所以能跳到s[1]和s[2]的位置，即3,1在BFS的同一层。s[1]=3能跳到除了该层的s[3]和s[4]，即1,4在BFS的下一层；s[2]=1无法跳出第二层。因为4在最后一层，也就是第3层，所以最少可以2步到达。
2
3,1
1,4代码如下：
class Solution {
public:
int jump(vector<int>& nums) {
int level = 0, current_fastest = 0, next_fastest = 0;
int n = nums.size(), i = 0;
if (n == 1)return 0;
while (true) {
++level;
while (i <= current_fastest && i < n) {
next_fastest = max(next_fastest, i + nums[i]);
++i;
}
if (next_fastest >= n - 1)return level;
current_fastest = next_fastest;
}
return 0;
}
};
本代码提交AC，用时8MS。由于i指针一直在往前走，所以时间复杂度为O(n)。
三刷。 依然是BFS的思路，代码简洁易懂：
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int step = 0, pre_max = 0, next_max = 0;
for(int i = 0; i < n; ++i) {
if(i > pre_max) {
++step;
pre_max = next_max;
}
next_max = max(next_max, i + nums[i]);
}
return step;
}
};本代码提交AC，用时28MS。
Pingback: LeetCode Jump Game | bitJoy > code